CS 146 Spring 2004 Homepage

CS 146 Data Structures

Green Sheet for Spring 2004 Course Schedule for Spring 2004 Spring 2004 Computer Assignments: Computer Assignment 1 Computer Assignment 2 Computer Assignment 3 Computer Assignment 4 Computer Assignment 5 -- updated information about I/O (4/22/04) 2003 Computer Assignments: Computer Assignment 2 (Spring 2003) Computer Assignment 3 (Spring 2003) Computer Assignment 4 (Spring 2003) Make-up Program Computer Assignment Student Programs: Assignments done by Justin Corpron Extra Credit If you did not do well on Midterm 3 and wish to do an extra credit assignment, then email me at sin_min_lee1@yahoo.com Study Guides: Spring 2004 Midterm 1 Study Guide Spring 2004 Midterm 2 Study Guide Spring 2004 Midterm 3 Study Guide Spring 2004 Final Exam Study Guide Spring 2003 Midterm 1 Study Guide Spring 2003 Midterm 2 Study Guide Spring 2003 Midterm 3 Study Guide Spring 2003 Final Study Guide Lecture Notes: Lecture 1 - Mathematical Induction Lecture 2 – Chip Firing Game “The Story of JAVA by James Gosling”/a> Java: Past, Present & Future“ by James Gosling “Java In An Hour” by Charlie McDowell “Chip-firing Java Applet game.” (Note: If this game doesn't work under IE browser, then try Netscape browser.) Lecture 3 – Introduction to Complexity Insertion Sort Animator Lecture 4 – Algorithm and Analysis Run Time Analysis Runtime Efficiency Lecture 5 - Big-oh notation Example Algorithm Big-O and Recurrences Algorithms and Problems Analyze Lecture 6 - Graph Theory Partition of Integers Planar / Non-Planar Graphs Lecture 7 - Trees Trees and tree traversals Lecture 8 - Sorting Binary Tree 2 Insertion & Shell Sort (By: Andy Le) Robert's Sorting Presentations Saad's Sorting Presentation Chen's Recursion Justin's Merge Sort Presentation Pedro's Heap Sort Presentation Merge Sort vs. Other Sorts Sedegewick’s “Permutation generated methods” Lecture 9 - Recursive Algorithms Recursive and Merge Sort Lecture 10 - Midterm 2 Review Lecture 11 - Polynomials and Tree Sort Tim's Presentation on polys Lecture 12 – 13 AVL Trees [L12] – AVL Trees [L13] – AVL Trees Cont. AVL-Tree Animation Tin Ho's AVL Tree Presentation Chien-Pin Hsu's AVL Tree Presentation Chirag's AVL Tree Presentation Asami Enomoto's AVL Tree Presentation Lecture 14 – 2-3-Tree Damien's 2-3 tree presentation Xinlin's b-tree presentation Lecture 15 – Graph Coloring Jong Seok's Graph Coloring Presentation Lecture 16 – Red Black Tree Tutorial Dan's Red Black Tree Presentation Red Black Tree Demo Applet Lecture 17 – Data Compressor [Huffman] Data Compression By Gabriel Laden Hae-Sun Jung's Data Compression Lecture 18 – Greedy Algorithm Lecture 19 – Minimum Spanning Trees Greedy Algorithm Presentation by Regina's MST Presentation John's MST Presentation Lecture 20 - Heap and Heapsort Lecture 21 – Shortest Path Algorithm Shortest Path Algorithm Shortest Path Algorithm Cont. Shortest Path problem for Dijkstra, Bellman Ford and other Algorithms Good website for data structure conncepts Very good website for Interractive Link List Demo Java Applet for Dijkstra, Prim and Kruskal Algorithm. Lecture 22 – Topological Sort Dynamic Programming 1 (Posted 4/22/2004) Dynamic Programming 2 (Posted 4/22/2004) Lecture 23 – Queues and Stacks Application of Queues ans Stacks BFS Applet Jimmy Lu's Presentation Presentation by Ryan Morris Dan Nguyen Stack Application Presentation Lecture 24 – 25 NP Problem [L24] NP Complete Problem [L25] NP Complete Problem 2 NP – Complete Problems Complexity, Computability, and Intractability Intractability - A compendium of NP Optimization Problems NP Complete Problem (Posted 4/22/2004) Lecture 26 – Primality Test A Prime Solution The PRIMES is in P Primes is P story 2 Miller-Rabin Test Primality Testing Wai Cheung and Ching Ho Presentation Lecture 27 – Midterm 3 Revision Lecture 28 – Shortest Path Calculation in Graphs Lecture 29 – Hashing Table Phillip and Truong Nguyen Topological Sort and Hashing Lecture 30 – NP Problems Lecture 31 – Graph NP Students’ Presentations: Advanced Data Structures Java Profiling By Gabriel Laden Useful links Kruskal’s and Prim’s Algorithm Kruskal’s Algorithm and Demo Files Discussion of Sorting Algorithm Sorting Algorithms Sorting Algorithms: Java Demo Tree Traversals Binary Tree Traversal Animation Applet Binary Tree Java Example Binary Tree Animation File John Jacky: Links on Data Structures and Algorithms National University of Singapore Links on Algorithms from various Universities Erhan Erdem: Data Structures and Algorithms Professor Morris: Lecture Notes Professor John Morris: Data Structures and Algorithms Dictionary of Algorithms and Data Structures Data Structures for Computers Network Homepage of Algorithm Analysis Parallel Search Algorithm Effective Change of XML Algorithm Dijkstra’s Algorithm Allan Turing Paper Miscelanous Guidance note on Plagiarism - From School of Computer Science, The University of Birmingham Talking in Code [ Interview with B. Stroustrup] Beautiful Life SARS Note: All the following contents have not been updated. Introduction to Design and Analysis of Algorithms(1) Introduction to Design and Analysis of Algorithms(2) Asymptotic analysis of time complexity What is Asymptotic Analysis? Asymptotics in the Analysis of Algorithms by William Shoaff with lots of help Efficient Algorithms for Sorting Data Structures and Algorithms More Efficient Sorting Algorithms Searching and Sorting Algorithms Sorting Arrays: Algorithms and Efficiency Efficient Algorithms for Searching Intelligent Search Algorithms Searching Arrays: Algorithms and Efficiency Algorithm analysis: Worst and Average Case Analysis Average-case analysis & algorithms Worst case Analysis of Algorithms: Average Case Analysis Recurrences and Asymptotics Mathematical Background Data Structures (Balanced Trees) Almost Balanced Trees AVL balanced trees PlanetMath (Definition for Balanced Tree) Data Structures and Algorithms: Heaps Data Structure and Algorithms: Hash Table Data Structures(1) Data Structures(2) Algorithm design techniques Tutorial on Dynamic Programming Dynamic Programming Page Greedy Algorithms(1) Greedy Algorithms(2) Lecture 9 - On Raising a Number to a Power Note on recurrence relations Lecture 10 - Graph Theory 1 Lecture 10 - Graph Theory 2 Basic concepts Terminology Representations of graphs Lecture 11 - DFS and BFS Spring 2002 Extra Credit Lecture 12 - Graph Isomorphisms representation graphs Lecture 13 - Connectedness Spring 2002 Extra Credit 2 Lecture 13 - Connectivity Lecture 14 - Eulerian and Hamiltonian Lecture 14 - Euler and Hamiltonian paths Lecture 15 - Dijkstra’s algorithm Lecture 16 - Minimum Spanning Trees Lecture 17 - Graph coloring Lecture 17 - Chromatic number