Time: Thu, 5:30pm - 8:15pm
Location: Olsen 103
Yongfeng Zhang (firstname.lastname@example.org)
Office: Olsen 216
Office hour: Fri, 2:30pm - 5:00pm, or by appointmnet
This is a required course for Computer Science majors. It builds on the introduction to data types and data structures that students receive in Computing II (COMP 1020).
In this course (COMP 4040) we distinguish between an abstract data type (such as a list, stack, queue, tree, or hash table) and a data structure that represents how the abstract data type is represented and stored in the computer's memory. We learn about algorithms for manipulating information in a variety of fundamental abstract data types and data structures.
Information tasks such as searching, retrieving, inserting, updating, sorting and deleting arise frequently in Computer Science problems that are central to many computer applications. We focus on algorithms to correctly and efficiently accomplish these types of core tasks.
What do we mean by "efficiently?" We measure efficiency in terms of speed and space (storage) usage. We use techniques from theoretical computer science and discrete mathematics for our analyses.
Why does efficiency matter in computing environments in which processors are very fast and storage space is abundant? Here are two reasons that have significant practical impact: 1) The amount of information continues to explode quickly, and for large amounts of information the differences in speed and storage requirements across different algorithm/data structure combinations can be huge; 2) Some types of problems are inherently difficult and we cannot expect to solve them as efficiently as we can solve easier ones. It is important to learn to recognize such problems and be familiar with ways to tackle them.
The algorithms we study represent a variety of important Computer Science problem-solving strategies, or algorithmic paradigms. We examine major characteristics of several algorithmic paradigms.
Algorithms, Data Structures, Time and Space Complexity Analysis
We have 4 homework assignments, 10 credits for each assignment. Assignments are posted on Fridays, you have two weeks to finish the homework, homeworks are due on the second Friday (14 days later) at 11:59pm.
|1||9/7||Algorithmic Analysis, Divide and Conquer I||Ch2, 3||Lecture 1|
|2||9/14||Divide and Conquer II, Solving Recurrences||Ch 3, 4.3-4.6||Lecture 2|
|3||9/21||Sorting Lower Bounds, Linear Sorting Algorithms||Ch8, 9||Lecture 3|
|4||9/28||Binary Search Trees, Red-Black Trees||Ch12, 13||Lecture 4|
|5||10/5||Randomized Algorithms I, Quick sort||Ch5, 7||Lecture 5|
|6||10/12||Randomized Algorithms II, Hashing||Ch11||Lecture 6|
|7||10/19||Graph Algorithms I, DFS/BFS/Dijkstra's||Ch22, 24.3||Lecture 7|
|8 & Midterm||10/26||5:30pm – 7:00pm, Olsen 311; Graph Algorithms II||-||Lecture 8|
|9||11/2||Greedy Algorithms I, Proof of Correctness||Ch16.1, 16.2, 16.3||Lecture 9|
|10||11/9||Greedy Algorithms II, Minimum Spanning Tree||Ch23||Lecture 10|
|11||11/16||Dynamic Programming I, Bellman-Ford/Floyd-Warshall||Ch25.2, 15.1||Lecture 11|
|-||11/23||-||No class, Thanks giving day||-|
|12||11/30||Dynamic Programming II, LCS/Knapsack||Ch15.4||Lecture 12|
|13||12/7||Maxflow/mincut, Final review||-||Lecture 13|
|-||12/14||-||Reading Day, QA|
|Final Exam||12/15||Time: 6:30PM - 9:30PM, Location: Olsen 311||-||-|
Last update: 12/08/2017