Introduction to algorithms
Math 199, Spring 2018
Lectures: 10:00-10:50am in MSTB 226 or 2:00-2:50pm in SBSG 241
Instructor: Christopher Davis, daviscj@uci.edu, Rowland Hall 440J
Office hours: No specific office hours for this class, but you're welcome in the office hours for my other classes, which are Mondays 10am-11am in RH 440J and Tuesdays 11am-12pm in RH 340N.
Handouts:
- Recursion handout Download Recursion handout from http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/recursive.pdf Links to an external site.
Week 2 algorithms:
- Merging two sorted lists: https://en.wikipedia.org/wiki/Merge_algorithm#Merging_two_lists Links to an external site.
- Mergesort and Quicksort Download Mergesort and Quicksort from Algorithm Design Manual
- Selection sort Download Selection sort from Algorithm Design Manual
Week 3 algorithms:
- Algorithms involving graphs: Chapter 5 Download Chapter 5 of Algorithm Design Manual
- Introduction to Depth First Search and Breadth First Search: YouTube video Links to an external site.
- Finding a cycle in a directed graph: YouTube video Links to an external site.
Week 4 algorithms:
- Dynamic Programming for Fibonacci numbers: YouTube video Links to an external site.
- Dynamic Programming for Longest Increasing Subsequence: YouTube video Links to an external site. and Algorithm Design Manual excerpt Download Algorithm Design Manual excerpt (I believe there is a typo in the l_i table, I think it should begin 1,2,2,3 instead of 1,2,3,3)
Week 5 topics:
- The beginning of Chapter 3 on Data Structures Download Chapter 3 on Data Structures: Pay attention to everything in this section. Focus on how arrays and linked lists store the same type of data in very different ways, with each type having pros and cons. Pay special attention to the parts on comparing the efficiency of different dictionary operations using different types of data structures. Also read about Binary Search Trees.
- If there's time, we will also discuss Priority Queues and Heaps. This website from the University of Wisconsin Links to an external site. has a nice overview.
Week 6 topics:
- Weighted graphs and shortest paths
- Review of Breadth First Search. Why is it better than Depth First Search? Why doesn't it work for weighted graphs?
- Dijkstra's algorithm: Wikipedia entry Links to an external site. and video Links to an external site. and another video Links to an external site.
- Floyd-Warshall algorithm: Wikipedia entry Links to an external site. and video Links to an external site.
- Bellman-Ford algorithm: Wikipedia entry Links to an external site. and video Links to an external site.
- Thanks to Jonathan Vo for providing a copy of the slides Download slides from his presentation
Week 7 topics:
- There is no class meeting this week. Please watch the following video.
- Heaps and heap sort Links to an external site.
- Website on heaps Links to an external site.
- Here is a video Links to an external site. with a detailed example of heap sort
- Wikipedia entry Links to an external site. on heap sort
- Additionally, if you're not familiar with the precise meaning of Big O notation, please also watch the following videos.
- Formal definition of Big O notation Links to an external site.
- Working with the precise definition of Big O notation Links to an external site.
- Related concepts: Omega and Theta Links to an external site.
- Another introduction to Big O notation Links to an external site.
- A third introduction to Big O notation Links to an external site.
Week 9 - the subset sum problem:
- https://en.wikipedia.org/wiki/Subset_sum_problem Links to an external site.
- https://cseweb.ucsd.edu/classes/wi12/cse202-a/lecture7-final.pdf Links to an external site.
- https://youtu.be/s6FhG--P7z0
Links for the Coding assignment on the Weeks 1-4 material:
- https://algocoding.wordpress.com/2014/08/24/adjacency-list-representation-of-a-graph-python-java/ Links to an external site.
- https://www.youtube.com/watch?v=lBRtnuxg-gU Links to an external site.