CSE 250: Announcements


Last updated: Friday, May 6, 2011 11:34:41 AM EDT

1. Clarification on materials allowed for Final exam:

Test book.

Class notes posted at cse250 website.

The note you took from cse250 lectures and recitation classes.

No other materials are allowed (nor useful).

2. Project 4 due date.

TA will start grading Project 4 right after the due time (May 6, 11:59pm). You can submit project late upto Monday May 9 by 11:59pm, with penalty specified in syllabus. If you submit late, however, you must inform TA Jeff Delmerico by email. (Otherwise, he might miss you submition).

Last updated: Thu May 5 14:06:16 EDT 2011

1. HW6 solution has been posted.

2. For Project 4: When decode a Morse code message, you should use the Morse code tree, NOT from the code table.

Last updated: Monday, May 2, 2011 2:57:26 PM EDT

In the HW5 solution for Q3, it contains a few errors (in the last few figures, the number 15 should be 13). The solution has been corrected and re-posted.

Last updated: Saturday, April 30, 2011 9:25:59 PM EDT

1. HW5 solution has been posted.

2. HW6 due date: You can turn in your HW6 either on May 4, Wednesday 3 - 4 pm or May 5 (232 Bell),, Thursday 9am - 10am (232 Bell), during TA's office hours.

3. On May 5, Thursday, TA will hold two review sessions, at Bell 224 one from 3:30 - 4:30 and one from 4:30 - 5:30.

4. Final Exam Information:

TUE 05/10/2011, 08:00 AM - 11:00 AM, HOCH 114

Open book, open notes.

Comprehensive, but about 2/3 of weight will be on the topics covered after Midterm 2.

Bring your UB ID with you.

Review topics (for the material discussed after Midterm 2):


* definitions and order properties

* how each operation (insert(key), find(key1), remove(key)) works.

* Runtime of the insert, find and remove operations.


* definitions and order properties

* how each operation (insert(key), find(key1), remove(key)) works.

* When and why we need B-tree (vs Binary Search trees).

Prioriry queues and the Heap implementation

* basic operations of a Max (or Min) priority queue.

* basic definitions and order property of a heap.

* vector/array implementation of binary heap.

* How each operation works (insert(key), Find-Max() and delete-Max()), and their run time.

* How heapsort works

Hashing Table

* The considerations for designning a good hashing function.

* How to handle collisions (separate chaining, Linear Probing, Quadratic Probing)

* How each operation (find(key), insert(key), remove(key)) works. For the Linear and Quadratic Probing, why do we need lable each entry as "empty", "occupied" and "deleted"?

* What are the main problems with Linear and Quadratic probing.

Graph algorithms.

* basic definitions and terms

* the representations of graphs (Adjacency list and Adjacency matrix), the advantages and disadvantages of each.

* BFS and BFS tree, how it works and its applications.

* Dijstra's algorithm for solving the shortest path problem

* Minimum Spanning Tree problem

* Prim's algorithm, how it works and its run time.

* For both Djjstra's and Prim's algorithm, we use a (min) priority queue to keep certain information, why and how we do this?

Last updated: Tuesday, April 26, 2011 10:05:30 PM EDT

I have re-posted HW6, (the due time has been changed). Please re-print the new one.

Last updated: Tuesday, April 26, 2011 11:27:47 AM EDT

HW6 has been posted.

Last updated: Friday, April 22, 2011 8:31:37 AM EDT

1. Class note for Ch 12 has been posted.

2. For the remiander of this semester, My office hour has bben chnaged to Wed. and Friday 3-3:50.

Last updated: Wed Apr 13 15:15:18 EDT 2011

Project 3 solution has been posted (in Project section).

Last updated: Wednesday, April 13, 2011 10:47:38 AM EDT

1. HW5 has been posted.

2. Grade distributions for HW3, HW4, Project 2, Midterm 2 have been posted.

3. I'll be out of town April 14-18. Jeff Delmerico will teach class on April 15. The class on April 18 is cancelled.

Last updated: Monday, April 11, 2011 3:23:25 PM EDT

Project 4 (and some sample codes for it) have been posted.

Last updated: Wednesday, April 6, 2011 6:35:49 PM EDT

HW4 solution and Classnotes (for Chapter 9) have been posted.

Last updated: Monday, April 4, 2011 11:04:08 AM EDT

1. There are two typos1 in HW4:

Problem 4 (a): The Inorder traversal string should be: a / b - 3 * x / y

Problem 7. The value of h for the example tree should be h=2 (not h=3). (The corrected HW4 has been reposted.)

2. Midterm 2 will be on April 8. (I'll be out of town. TA will proctor the exam).

Last updated: Sunday, April 3, 2011 4:27:32 PM EDT

Midterm 2: Friday, April 8, 2:00-2:50.

* Closed book, Closed notes.

* Bring your UB ID.

* You may bring a calculator (but you don't really need one).

* The topics to be covered:

1. Runtime analysis:

(a) Definitions and properties of O, Theta and Omega

(b) Compare growth rate by using limit test method.

(c) Analyze simple loop structure by using summation.

(d) Estimate real runtime, from the growth rate and the real runtime of a sample run on small input size.

2. Sorting Algorithms

(a) For each sorting algorithm we studied (InsertionSort, BubbleSort, SelectionSort, MergeSort, QuickSort), know how they work;

(b) Know their worst case runtime, advantages and disadvantages.

3. "Dictionary" Data Structure.

(a) Basic definitions.

(b) We discussed several simple implementations of dictionary data structure: sorted array/vector, unsorted array/vector, sorted linked list, unsorted linked list. For each of these implementations, how the three basic functions of dictionary data structure work? What's the worset case run time?

4. BST Tree.

(a) definitions and order properties

(b) Inorder, preorder and post order traversal

(c) Simple functions for calculating information about binary trees (such as: height, number of leaf nodes, etc.)

(d) As an implementation of dictionary data structure, how each operation (insert(key), find(key), remove(key)) works, and their run time.

5. Basic ideas and concepts involved in Project 3 (not detailed programming level.)

6. Most Midterm II problems will be similar to the problems in HW3 and HW4, and the examples discussed in lectures.

Last updated: Thursday, March 31, 2011 11:01:20 AM EDT

Classnote for Chapter 11 has been posted.

Last updated: Tuesday, March 29, 2011 12:17:06 PM EDT

1. HW4 has been posted. The due date is April 6.

2. Midterm 2 will be on April 8 (as in the schedule). It will cover the material up to BST (Binary Search Tree). More details will be provided later.

3. There is a bug in the sample executable file "application" for Project 3 (in the folder /home/faculty/xinhe/cse250/Project3 on timberlake). (It works only if the name line contains no space.) It has been fixed. The new sample executable file is "application2". (The functionality remains exactly the same).

Last updated: Tuesday, March 22, 2011 11:54:24 AM EDT

1. HW3 and Midterm 1a solutions have been posted. (The solution of Midterm 1b is similar).

2. In the lecture on this Wed., I'll introduce the most foundamental concepts and ideas about data structures. These are neither in the book, nor in class notes. If you skip this class, it will be hard for you to understand what we are trying to do in the remainder of this class.

Last updated: Monday, March 21, 2011 1:26:14 PM EDT

The following have been posted:

1. Classnote for Chapter 8, Trees

2. Sample codes for measuring real runtime (for two Fib number functions and for sorting algorithms) are added in the Timer sub-directory.

Last updated: Fri Mar 11 10:22:51 EST 2011

The following have been posted:

1. Grade distribution for HW2 and Midterm 1.

2. Project 2 solution.

3. Projerct 3. The due date is April 4. This project is SIGNIFICANTLY longer than the previous projects. SO you should START EARLY.

Last updated: Mon Mar 7 09:42:42 EST 2011

1. Homework 3 and new sample codes (Timer) have been posted.

2. The submission instruction for Project 2 is exactly the same as Project 1.

Last updated: Mon Feb 28 19:06:43 EST 2011

HW 2 solution and grade distribution of HW1 and Project 1 have been posted.

Jeffrey Delmerico brought to my attention that there is a website (http://bcs.wiley.com/he-bcs/Books?action=index&bcsId=2949&itemId=0471467553) for the textbook that has all of the sample code that they develop in the chapters, which could be helpful for the students to have access to.

However, the website also has solutions for the odd-numbered problems on there, so the students would have answers to many of the homework questions.

I think some students alraedy know this website. To be fair, I am posting the link to the website. But from now on, I will not use odd-numbered questions in the book as HW problems.

Last updated: Mon Feb 28 11:17:48 EST 2011

1. Following have been posted:

* Project 1 solution

* Project 2.

* Classnote for Chapter 10.

2. HW1 has been returen to class last Friday (Feb 25). If you have question about grading, please talk to TA (Jeff) by Friday March 4.

3. Midterm 1: Friday, March 4, 2:00-2:50pm.

* Close book, close notes.

* Bring your UB ID cards.

* You may bring a calculator.

* The topics to be covered:1. Basic C++ syntax and concepts. Most problems in midterm 1 are similar to problems in HW1, HW2, Project 1, and the examples discussed in lectures. More specifically:

(1) basic syntax, control statements, basic i/o statements.

(2) pointers, new, delete.

(3) arrays

(4) function definitions, parameter passing methods

(5) Class definition

(6) copy contructor and assignment operator

(7) Template Class and template functions

(8) vector and string classes

(9) Class Inheritance and Hierarchies

(10) method overloading

Last updated: Sat Feb 26 22:41:50 EST 2011

HW 2 clarification:

In the last question (#9, pg. 238 Programming Problem 3), the book asks you to write a function called "delete" to find and remove an item from a vector. But "delete" is a C++ keyword, so if you try to compile the program, the compiler will give an error. The easy fix for this is to call it something else when the students are actually writing and testing the program (e.g. "delete_v" instead of "delete"),

Last updated: Mon Feb 21 11:58:50 EST 2011

HW2 and Classnote 4 have bben posted.

Last updated: Wed Feb 16 12:13:43 EST 2011

1. Midterm 1 is postponed one week: March 4, Friday, 2011, 2-2:30pm.

2. Homework 1 solution has been posted (in the Homework section).

3. More sample codes (Exeption.cpp and List-Iter) have been posted.

Last updated: Sun Feb 13 23:52:59 EST 2011

Project 1 description has been posted.

Last updated: Fri Feb 11 13:55:37 EST 2011

Classnote 3 and more sample codes have been posted.

Last updated: Wed Feb 9 13:05:40 EST 2011

Jeff's office hours this afternoon (Wed) from 3-4 pm is canceled (due to sickmess).

2. Additional sample codes have been posted.

Last updated: Fri Feb 4 13:48:26 EST 2011

Jeff will hold his office hour on Monday 4-5pm at 21 Baldy, starting coming Monday.

Last updated: Thu Feb 3 00:15:27 EST 2011

HW1 has been posted.

Last updated: Mon Jan 31 13:42:22 EST 2011

Class note 2 and more example codes have been posted.

Last updated: Mon Jan 24 12:18:30 EST 2011

More C++ program examples have been added in the "Examples Directory" section.

Last updated: Fri Jan 21 15:25:42 EST 2011

Recitation classes will start next week. During this week (Jan 24-28), all five recitation classes will meet. After that, the recitation class A4 (Mon. 9-9:50) will be cancelled. Students in A4 class can go to other recitation classes. You don't need to change your registration. Just let TA knows. If you can not go to other recitation classes, please make arrangment with TA so that your question can be answered during TA's office hours.

Welsome to CSE 250.