Objectives and learning outcomes
The main goals of this course are related with the students' understanding algorithms and data structures and their use for solving computational problems.
This curricular unit has as objectives to acquire knowledge about:
- algorithms, in particular sorting and searching algorithms, and evaluation of the complexity of algorithms,
- data structures such as linked lists, stacks, queues, unbalanced and balanced trees, heaps and graphs,
- how to select the most appropriate data structures, given a practical problem,
- how to select the most appropriate algorithms for a given set of data structures.
Upon the conclusion of the course, students shall be able:
- to have developed skills on using algorithms, particularly in problems involving sorting and/or searching,
- to assess the efficiency of the algorithms by analyzing the technical complexity, in order to select the most efficient algorithms to solve any given problem,
- to explain the requirements of efficiency and performance for algorithms and data structures,
- to analyse the computational (spatial, temporal) complexity of programs.
The C programming language will be used in the practical component of the course, although the concepts involved are independent of the language.
Contents/Syllabus
Algorithms
1. Complexity analysis of algorithmd: Big-O
2. Amortized analysis of algorithms
3. Sorting algorithms in lists implemented with arrays
3.1. Iteratives algoritms: Selection sort, and Bubble sort
3.2. Recursives algorithms: Merge sort, and Quicksort
4. Searching algorithms in lists implemented with arrays
4.1. Iteratives algoritms: Linear/Sequential search, and Binary search
4.2. Recursives algorithms: Binary search
Abstract Data Structures
1. Sequential access structures
1.1. Singly linked lists
1.2. Doubly linked lists
1.3. Stacks
1.4. Queues
2. Non-sequential access structures
2.1. Binary trees
2.2. Binary search trees
2.3. N-ary trees
Balanced Search Trees
1. Binary trees
1.1. Adelson-Velskii Landis (AVL)
1.2. Red-Black tree
1.3. Interval trees
2. 2-3 trees
Priority Queues (Heaps)
1. Heap
2. Binary heap
3. Binomial heap
Graphs
1. Types of graphs
2. Data structures for graph representation
3. Graph search algorithms
3.1. Breadth First Search
3.2. Depth First Search
4. Graph problems
4.1. Minimum Spanning Tree: Prim
4.2. Shortest Path: Dijkstra
4.3. Maximum Flow: Ford-Fulkerson
4.4. Optimal Matching Problem ("Stable Matching Problem"): Gale-Shapley
Bibliography
"Algorithms", 4th Edition, 2011
Robert Sedgewick and Kevin Wayne.
Addison Wesley.
ISBN-13: 978-0321573513
Antti Laaksonen
Draft July 3, 2018
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
MIT Press, ISBN-13: 978-0262033848
"Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", 3rd Edition, 2001.
By Robert Sedgewick
Addison-Wesley Professional
ISBN: 0201756080
Clifford A. Shaffer
Department of Computer Science, Virginia Tech
Assessment criteria
Learning period
- two written tests (WT): 16 points (8 points each)
- two practical tests (PT): 4 points (2 points each)
- Final Grade (FG): WT + PT
Exam
- Admission: FG >= 6
- Exam (E) - 16 points
- Final exam classification = E + PT
Calendar of assessment
- written test 1: April, 20; 6 pm
- written test 2: June, 01; 6 pm
- practical test 1: March, 23-27 (in practical class room)
- practical test 2: Mai, 04-08 (in practical class room)
Notes
Algorithms
Abstract Data Structures
Balanced Search Trees
Priority Queues (Heaps)
Graphs
Graph search algorithms
Graph problems
Practical class
Visualizations of the data structures and algorithms
Practical class in portuguese language
Practical assessment
Carrying Out Practical Tests
Assessment Platform
Service hours
- Monday, 4 pm to 6 pm (Office 4.2)
- Tuesday, 11 am to 1 pm (Office 4.2)