CSCI 2410 Data Structures and Algorithms, Spring 2009

 

Instructor:

Dr. Y. Daniel Liang
y.daniel.liang@gmail.com

Computer Science Dept

Lecture Sessions:

Section 01 MWF 10:00-11:50 SC 1503B

Textbook:

Introduction to Java Programming Comprehensive Version, Seventh Edition, Y. Daniel Liang, Prentice Hall, May 2008

Course Description 

Implementation and analysis of data structures and algorithms. Topics include: recursion, generics, linked lists, stacks, queues, hash tables, trees, heaps, various sorting algorithms, and time and space complexity analysis. Use of application program interfaces (API's).

Goals 

The goals of this course are that students, by mastering the topics presented in this course, apply appropriate data structures to develop efficient algorithms.

Course Objectives 

Upon successful completion of this course, students will be able to use array lists, linked lists, stacks, queues, priority queues, sets, maps, binary trees, and hashing to implement projects. OOP and gain practical skills to solve real-world programs using Java. Students will also be able to analyze algorithms and use the big-O notation to express the worst case running time and space needed by an algorithm.

Prerequisites 

CSCI 1302 Advanced Programming Principle and Math 1161 Calculus I

Tentative Schedules  

WEEK TOPIC REQUIRED READINGS
1

L1: Review of OOP

Chapters 7-17
 

L2: Review of OOP

Chapters 7-17
2 L3: Recursion Chapter 20

 

L3: Recursion

Chapter 20
3

L3: Recursion

Chapter 20
  L6: Generics Chapter 21

L7: Generics

Chapter 21
 

L8:  Free time (University  or federal holidays)

 
L9: Collections framework, Collection, Set, HashSet, TreeSet, LinkedHastSet, Iterator Chapter 22
L10: List, ArrayList, LinkedList Chapter 22
6

L11: Map, HashMap, TreeMap, LinkedHashMap

Chapter 22

Exam 1 and Post-Exam Review  
 7 L12: Big O notation Chapter 23
  L13: Design efficient algorithms Chapter 23
8 L14: Sorting Chapter 26
  L14: Implementation of ArrayList and LinkedList Chapter 24
 9

L16: Binary Search Tree, search, and insertion

Chapter 26
  L17: Heaps and Priority Queues Chapter 26
10 

Exam 2 and Post-Exam Review

 
 

L18:  Graph algorithms

Chapter 27
11

L19: DFS and BFS

Chapter 27

  L20: Weighted graphs Chapter 28
12

L21: Minimum spanning trees

Chapter 28
 

L22: Shortest paths

Chapter 28
13 L23: AVL trees Handouts
  L24: Splay trees Handouts
14 Hashing Handouts
 

Hashing

Handouts
15 Review for Final Chapter 17, S17.6-17.7
  Review for Final  
  Final Exam  

Evaluation Scheme

Evaluation is based on attendance, programming exercises, midterm exams, and final exam. Evaluation scheme is subject to change with a prior notice.

Attendance will be checked randomly. Missing 20% of classes will result in 5% of deduction of the overall grades. Missing 40% of classes will be automatically dropped out of class.

Programming assignments must be done individually.  Source file printout  must be submitted in the class on the due day regardless its status (complete or incomplete). No makeup will be offered except under extraordinary situations. In addition to submitting a hard copy, students must also submit the programs to LiveLab. Your grades will be recorded on LiveLab.

Exercises

40% (Due dates will be announced in the class.)

Two Midterm Exams  15% Each (50 minutes each)
Final Exam 25%  (2 hours)
Class Attendance 5% (Attendance will be checked regularly. Missing classes frequently will be automatically dropped out of class.)

 

Grade

Points

A

>= 90.0

B >=80.0
C >=70.0
D >=60.0
F <60.0

Programming Documentation and Style

Click here to see Programming Documentation and Coding Style.

Grading Policy

If a program can be automatically graded, LiveLab will assign a score. Partial credits may be justified for some cases. If a program cannot be graded automatically, it will be graded manually and a score will be entered in LiveLab.

Grading Policy

20% on Programming Style and Documentation.

80% on Correctness.

Academic Honor Code

Programming assignments must be done individually. Failure to do so will result in a violation of the AASU Academic Honor Code. The following cases will be considered as violations: identical code, and extremely similar code. Violations will be reported to the Office of Vice President of Student Services.

Attendance Policy

Attendance is mandatory. Send me (y.daniel.liang@gmail.com) an email in advance if you have to miss a class due to emergency or sickness. Please arrive in the class at least three minutes before the class.