ICS220 Data Structures and Algorithms

Welcome to Data Structures and Algorithms.

Instructor: Dr. Vaide Narvaez

Schedule: Tuesday and Thursday 8:30-10:00am

Course Description

An understanding of data structures and algorithm analysis will be presented in the following topics: stacks queues, recursion, linked lists, trees, graphs, sorting and searching.  This will serve as the basis for further studies in information systems and approaches using an application perspective.  Case Studies are required.

Course Objectives

The course will cover:

  • basic algorithm analysis (e.g., asymptotic analysis of upper and average complexity, big-O, little-o, omega, and theta notation);
  • general algorithm strategies such as brute-force algorithms, greedy algorithms, divide-and-conquer, and dynamic programming;
  • fundamental computing algorithms including numeric computations, searching and sorting, graph algorithms, and string matching; introduction to data structures, covering stacks, queues, linked lists, and rooted trees; advanced data structures, including B-trees and heaps.

Course Syllabus and Material

Course Syllabus

Week Content Exercises/Assignments/Additional Material
1 Lecture 1: The role of algorithms in computingLecture 2: Java: a crash course
2 Lecture 1: Arrays vs. Linked ListsLecture 2: Analyzing Algorithms
  • Code skeletons for the Java exercise: ArrayTemplate.java and ListTemplate.java
  • Read Sections 2.1 and 2.2 from [1]
3 Lecture 1&2: Growth of functions: Asymptotic notation
  • Do exercises in the slides
  • Read Section 3.1 from [1]
  • InsertionSort implementation
4 Lecture 1: Elementary data structures: Stacks and QueuesLecture 2: Linked Lists

Important!!:The queue is full when head=tail+1, which allows one empty cell in the array. If we allow to enqueue in such a case, we wont be able to distinguish between empty and full queues.

  • Read Sections 10.1 and 10.2 from [1]
5 Lecture 1&2: Hash tables
  • Read Sections 11.1, 11.2, 11.4 from [1]
6 Lecture 1&2: Binary search trees
7 Lecture 1&2: Sorting algorithms
  • Assignment 2 (Due 29.07.2010)
  • Read Chapter 6, Sections 7.1-7.2
8 Lecture 1&2: Elementary Graph AlgorithmsMidterm review
  • Read Sections 22.1-22.4
9 (No classes this week!!!)
10 Lecture 1: Minimum Spanning TreesLecture 2: Single source shortest paths(1)
  • Read Chapter 23 from [1]
  • Read intro to Chapter 24 from [1]
11 Lecture 1: Single source shortest paths(2)Lecture 2: All pairs shortest paths
12 Lecture1: B-TreesLecture 2: B-trees: Basic operations
13 Lecture: String Matching
  • Assignment 4 (Due 14.09.2010)
  • Read Sections 32.1, 32.4 from [1]

Important!!!:Assignment 4, question 3, assume the B-tree is of minimum degree t=3

14 Lecture 1&2: Red-Black Trees
  • Read Chapter 13 from [1]
15 Review

Reading Material

Required textbook

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms. 2nd edition, 2001 MIT Press.

Supplementary reading materials

  1. Robert Lafore, Data structures and algorithms in JAVA, 2nd edition, 2003, Sams Publishing.
  2. Adam Drozdek, Data Structures and Algorithms in C++, 3rd edition, 2005, Thomson Course Technology.
  3. Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, Algorithms, 2006, McGraw-Hill.