# Cse 310 Assignment 2 Solutions

### Catalog Description

Advanced data structures and algorithms, including stacks, queues, trees (B, B+, AVL), and graphs. Searching for graphs, hashing, external sorting.### Pre-requisites

Computer Systems Engineering BSE, Computer Science BS, Computational Math Sciences BS or Biomedical Informatics BS student; CSE 205 with C or better; MAT 243 with C or better (CMS students may substitute MAT 300) or CSE Graduate students.### Course Abstract

Data Structures and Algorithms is a fundamental course to CSE majors. Students will learn important techniques to store data and to process data efficiently. Data structures and algorithms cannot be separated. On one hand, good data structures help in the design of efficient algorithms. On the other hand, good data structures are discovered during the design of efficient algorithms. This course will cover three main concept areas i) Complexity analysis of algorithms, ii) Recursive Algorithms, and iii) Sorting and graph algorithms.This course requires a lot of work. Depending on different knowledge levels the students may have, all students may not be required to spend the same amount of time on this course. Every student is encouraged to preview before the class and review immediately after the class. Students are encouraged to ask questions in class, and to fully use the office hours of the instructor and the TAs. Students may also ask questions via email to the instructor and/or the TAs. There will be closed book tests and many heavyweight homeworks. Homeworks may involve theoretical contents as well as programming contents. The instructor will also assign suggested readings/exercises after each lecture.

### Textbook

Cormen, T. H., Leiserson, C. E., and Rivest, R. L., C. Stein, Introduction to Algorithms, 2nd edition, McGraw Hills and MIT Press. ISBN-10: 0262032937 ISBN-13: 978-0262032933.### Prerequisites

CSE205 (programming in C or C++), MAT243 (theorem proving)### Grading

- 6 Homeworks (5% each): Total 30%

Will be given on Monday, and to be submitted next Monday in class. Can be programming assignments. Preferably use C/C++. - 2 Midterm (20% each): Total 40%

Closed books/notes/internet 2 1/2 hour in-class exam - 1 Final (30%): Total 30%

Comprehensive Exam

### Course Learning Outcomes

Students who complete this course can:- define data structures (types) such as heaps, balanced trees, hash tables.
- explain how to use a specific data structure in modeling a given problem (e.g. I can explain how to model a dictionary using balanced trees).
- identify, construct and clearly define a data structure that is useful for modeling a given problem.
- state some fundamental algorithms such as merge sort, topological sort, Prim's and Kruskal's algorithm, and algorithmic techniques such as dynamic programming and greedy algorithms.
- use a specific algorithmic technique in solving a given problem (e.g. I can write a dynamic program that solves a shortest-path problem).
- design an algorithm to solve a given problem.
- define the notions of worst-case/best-case/average-case running times of algorithms.
- analyze and compare different asymptotic running times of algorithms.
- analyze a given algorithm and determine its asymptotic running time.
- combine fundamental data structures and algorithmic techniques in building a complete algorithmic solution to a given problem.
- create several algorithmic solutions to a given problem and choose the best one among them according to given requirements on time and space complexity.

### Major Topics and Time Covered

- Asymptotic Notation (1.5 hrs)
- Recursion, recurrence relations (3 hrs)
- Worst-case Analysis (3 hrs)
- Sorting (4.5 hrs)
- Median, Selection Problems: More on Divide-and-Conquer Algorithms (2.5 hrs)
- Hash Tables (2.5 hrs)
- Binary Search Trees, Red-Black Trees (4.5 hrs)
- Longest Common Subsequence: Introduction to Dynamic Programming (2.5 hrs)
- Graph Algorithms: Depth-first and breadth-first search, min. spanning trees, shortest path (9 hours)
- Disjoint Sets (union-find): Introduction to Amortized Analysis;
- String Matching (time permitting)

### Grade Appealing

Your grades will be posted at the class website, available to you. Whenever the grade for a particular work is available, we will post an announcement. You will have one week to challenge the grade in writing. If you do not contact either the instructor or the TAs within a week, there would be no change to your grade for that particular work. This applies to all of your graded work. It is your responsibility to keep the graded hardcopy of your work, except the last test.### Policy on Tests

All homework assignments are due before the lecture on its due date. No late assignment will be accepted. Final is pre-scheduled by the University and will not be changed. The dates of midterms will be announced in class one week before the test. In general, there will be no makeup test.### Brief Summary of the University Policies on Cheating

Any incidence of cheating in this class will be severely dealt with. This applies to homework assignments and tests. The*minimum*penalty for cheating will be that the student will not obtain any credit for that particular assignment (This means that if in a test and/or assignment a student is found to have cheated, he/she will obtain zero in that test and/or assignment). Students are encouraged to discuss with others the materials covered in class. However students should not discuss problems in assignments/tests. One tends to get very suspicious if two identically wrong results show up in the homework assignment and/or tests.

**Last Updated:** Aviral Shrivastava, 05/2010

## Spring 2010 CSE370 Wireless and Mobile Networks

**Locations and Hours:**

Monday and Wednesday, 3:50pm-5:10pm @ Stony Brook Union 226

**Instructors:**

Instructor: Prof. **Jie Gao**, 1415 . Email: jgao at cs dot sunysb dot edu. Office hour: Monday, Tuesday 5:30-7pm.

**Announcements:**

- Solutions for homework 3 and 4 have been posted on blackboard.
- Class on Monday April 12th will be moved to CS2313A ---- this is on the 2nd floor of CS building, opposite to CS2311.
- Solutions for homework 1 and 2 have been posted on blackboard.
- Homework 3 is due on Monday 15th.
- For homeworks due on Mondays, you may submit the homework after my office hour (starting at 5:30pm on Monday).
- First class on Monday Jan 25th, 2010.

**Course Description:**

**Prerequisites:**

CSE 310, Data Communication and Networks (or an equivalent course). Review materials fromCSE 310: CSMA/CD, Ethernet LAN, Routing protocols, IP, TCP.

**Course Materials:**

- Textbook: Jochen Schiller, Mobile Communications, 2/e, Addison-Wesley, 2003 (required)
- Kurose and Ross, Computer Networking: A Top-Down Approach, Addison-Wesley (optional).
- Principles of Wireless Networks, Pahlavan and Krishnamurthy, Prentice Hall, 2002 (optional).
- Papers from literature and handouts distributed in class, posted in this web page, or kept in library reserve.

**Grading and Requirements:**

Grading includes a late midterm exam (30%), homework assignments (40%), and a class project (30%). There is no final. Late homework gets 25% penalty per day.

**Syllabus:**

| Lecture Topics | Required readings | Notes |

1/25 | Introduction | Handout 0, Chap 1 | Slides |

1/27 | Signals, signal propagation | Handout 1, Chap 2.1-2.4 | Slides |

2/1 | Signal propagation (cont.), Modulation | Chap 2.6, What is dB? | Slides |

2/3 | Modulation (cont.) Intro to coding theory | Handout 2 on Reed Solomon Codes | Slides, Homework 1 |

2/8 | Reed Solomon Codes | ||

2/10 | No class due to snow storm | ||

2/15 | DSSS | Chap 2.7, Handout 3 on DSSS | |

2/17 | CDMA, MAC introduction | Walsh code, Slides, Chap 3.1-3.3 | Homework 1 due Homework 2 out |

2/22 | Aloha, Slotted Aloha | Analysis of ALOHA and slotted ALOHA, Chap 3.4. Slides Handout 4 on MAC, and ALOHA | |

2/24 | CSMA | Slides | |

3/1 | 802.11 | Chap 7.3, Slides | Homework 2 due Homework 3 out |

3/3 | Ad hoc network | Slides, paper on SSCH | |

3/8 | Location management | Chap Slides, Notes | |

3/10 | Mobile IP | Slides | |

3/15 | Network routing | Slides, link reversal paper | Homework 3 due Homework 4 out |

3/17 | DSR | Slides | |

3/22 | GPS | Slides | |

3/24 | Geographical routing | Slides | |

4/5 | Mobile TCP | Slides | Homework 4 due |

4/7 | Midterm review | ||

4/12 | Programming project, introduction to ns-2 @CS2313A | ||

4/14 | Midterm exam, in class | ||

4/19 | Programming project | Project, due may 16th | |

4/21 | Wirelss security I | Lecture notes | |

4/26 | Wireless security II | Slides | |

4/28 | Programming iPhones, by Guozhu Luo | ||

5/3 | |||

5/5 |

Reading List:

MAC:

- [BDSZ94] "MACAW: Media Access Protocol for Wireless LANs," V. Bharghavan and A. Demers and S. Shenker and L. Zhang, Proceedings of the ACM SIGCOMM Conference, 1994.
- [CWKS97] "IEEE 802.11 Wireless Local Area Networks", B. Crow, I. Widjaja, J. Kim, P. Sakai, IEEE Communications Magazine, Volume: 35 Issue: 9 , Sept. 1997.
- [BCD04] "SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks," Victor Bahl, Ranveer Chandra, and John Dunagan, Proc. of ACM Mobicom 2004, Sept.-Oct. 2004.

__Ad hoc networks:__

- Building a Rural Wireless Mesh Network: A do-it-yourself guide to planning and building a Freifunk based mesh network, wiki.
- Link Reversal Algorithms:
- The original paper: Gafni and Bertsekas, Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology, IEEE Transactions on Communications, Vol Com-29, No.1, Jan, 1981.
- The analysis of the convergence time in full/partial link reversal algorithm: Busch, Surapaneni, Tirthapura, Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks, SPAA, 2003.
- Find the minimum set of links to reverse so as to re-establish a DAG: Sukhamay Kundu, A distributed O(|E|) Algorithm for Optimal Link-Reversal, Distributed Computing and Networking, 2009.

__Geographical routing:__

**[Karp00]**Karp, B. and Kung, H.T.,**Greedy Perimeter Stateless Routing for Wireless Networks**, in Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243-254.*GPSR: one of the first on geographical routing.*

- http://www.mobilebehavior.com/2010/04/20/urban-sensing-building-systems-for-mobile-crowdsourcing/
- http://www.mobilebehavior.com/2009/11/05/trend-stealth-crowdsourcing/

## 0 thoughts on “Cse 310 Assignment 2 Solutions”