Modiwl ICP-2027:
Data Structures and Algorithms
Ffeithiau’r Modiwl
Rhedir gan School of Computer Science and Electronic Engineering
10 Credyd neu 5 Credyd ECTS
Semester 2
Trefnydd: Dr Ik Soo Lim
Amcanion cyffredinol
To allow students to use, select, implement and analyse a range of common abstract data types and algorithms.
Cynnwys cwrs
• Data Types, Abstract Data Types, Theory, implementations and uses of stacks, queues, lists, trees, graphs, hash tables, binary search trees. Constraints and Trade offs (time vs. space).
• Criteria for algorithms. Recursive algorithms: Towers of Hanoi. Data processing algorithms: sorting and searching. Graph theoretic algorithms: traversal, shortest path.
• Efficiency measures for time and space: rates of growth; asymptotic behaviour, big-O notation. Algorithm complexity classes (P, NP, NP-complete).
• New versions of algorithms, moral problems and dilemmas of updating an algorithm, moral responsibility of correctness. And understanding how to result ethical problems of algorithm and data structure development.
Cyswllt Canlyniad dysgu i Meini Prawf
threshold 40% |
good 60% |
excellent 70% |
|
---|---|---|---|
Show an understanding of a selection of common Abstract Data Types (ADTs) by appropriate selection and manipulation. |
Can state basic definitions of DT and ADT. Can describe the structures of the given ADTs and their basic uses. Knows the difference between static and dynamic implementations. | Can select an appropriate ADT and implementation for a given problem taking into account the trade offs involved. Can implement the given data structures. | Can design and implement new data structures based on the given ones. |
Show an understanding of the design and implementation of a selection of common algorithms. |
Can describe the basic operation of the given algorithms. | Can select and implement an appropriate algorithm for a problem. | Can design and implement new algorithms based on the given ones. |
Use complexity analysis to assist in the selection and design of algorithms. |
Can rank big-O complexity classes correctly. Can state the complexity of basic algorithms. Can select algorithms appropriately. | Can calculate complexity for simple cases. Understands the nature of NP-complete and computationally impossible problems. | Can calculate complexity for complex cases (divide and conquer). |
Understand the ethical issues of algorithms and the responsibility of the developer. |
Explain areas where moral dilemmas may occur, such as updating an underlying data structure or locating an error in a current algorithm. | Able to discuss various issues and provide realistic solutions and well formed argument. | Able to discuss various ethical issues, where they may occur. |
Dulliau asesu
Math | Enw | Disgrifiad | Pwysau |
---|---|---|---|
Examination | 60 | ||
Assignment 1 | 20 | ||
Assignment 2 | 20 |
Strategaeth addysgu a dysgu
Oriau | ||
---|---|---|
Lecture | Interactions via questions-and-answers. |
20 |
Private study | 40 | |
ASSESSED assignments, including tutorial questions, problems, essays etc. |
40 |
Sgiliau Trosglwyddadwy
- Rhifedd - Medrusrwydd wrth ddefnyddio rhifau ar lefelau priodol o gywirdeb
- Defnyddio cyfrifiaduron - Medrusrwydd wrth ddefnyddio ystod o feddalwedd cyfrifiadurol
- Hunanreolaeth - Gallu gweithio mewn ffordd effeithlon, prydlon a threfnus. Gallu edrych ar ganlyniadau tasgau a digwyddiadau, a barnu lefelau o ansawdd a phwysigrwydd
- Archwilio - Gallu ymchwilio ac ystyried dewisiadau eraill
- Dadansoddi Beirniadol & Datrys Problem - Gallu dadelfennu a dadansoddi problemau neu sefyllfaoedd cymhleth. Gallu canfod atebion i broblemau drwy ddadansoddiadau ac archwilio posibiliadau
- Cyflwyniad - Gallu cyflwyno gwybodaeth ac esboniadau yn glir i gynulleidfa. Trwy gyfryngau ysgrifenedig neu ar lafar yn glir a hyderus.
- Dadl - Gallu cyflwyno, trafod a chyfiawnhau barn neu lwybr gweithredu, naill ai gydag unigolyn neu mewn grwˆp ehangach
- Hunanymwybyddiaeth & Ystyried - Bod yn ymwybodol o'ch cryfderau, gwendidau, nodau ac amcanion eich hun. Gallu adolygu ,cloriannu a myfyrio'n rheolaidd ar eich perfformiad eich hun ac eraill.
Adnoddau
Goblygiadau o ran adnoddau ar gyfer myfyrwyr
Hard copies of the main course text are available at the library. On-line access to the highly recommended book is available.
Rhestrau Darllen Bangor (Talis)
http://readinglists.bangor.ac.uk/modules/icp-2027.htmlRhestr ddarllen
Main Course text: Java collections: an introduction to abstract data types, data structures, and algorithms - David A. Watt, Deryck F. Brown c2001
Highly Recommended: Introduction to algorithms - Thomas H. Cormen 2010, c2009
Recommended: Probability and Computing, by Michael Mitzenmacher and Eli Upfal, Cambridge University Press.
Cyrsiau sy’n cynnwys y modiwl hwn
Gorfodol mewn cyrsiau:
- H612: BEng Computer Systs Eng (3 yrs) year 2 (BENG/CSE)
- H61B: BEng Computer Sys Engineering (4yr with Incorp Foundation) year 2 (BENG/CSE1)
- G400: BSC Computer Science year 2 (BSC/CS)
- G40B: BSc Computer Science (4 year with Incorporated Foundation) year 2 (BSC/CS1)
- H64B: BSc Computer Sys Engineering (4yr with Incorp Foundation) year 2 (BSC/CSE1)
- GN41: BSC Computer Science for Business year 2 (BSC/CSFB)
- GN4B: BSc Computer Science for Business (4 year with Incorp Found) year 2 (BSC/CSFB1)
- I102: BSc Computer Science (with International Experience) year 2 (BSC/CSIE)
- GW49: BSC Creative Technologies year 2 (BSC/CT)
- H661: MEng Control and Instrumentation Engineering year 2 (MENG/CIE)
- H617: MEng Computer Systs Eng (4 yrs) year 2 (MENG/CSE)
- H619: MEng Computer Systems Engineering (with International Exper) year 2 (MENG/CSEIE)