CS 213 + CS 293 Lecture and Laboratory Plan

Milind Sohoni

My webpage.

`email: sohoni@cse.iitb.ac.in`

Detailed link for lectures link, and labs link.

Contact details of TAs: pdf.

My webpage.

Detailed link for lectures link, and labs link.

Contact details of TAs: pdf.

- What is data and what is not data. Real objects and processes vs. their representation. Different types of "data", viz., observations, designs, plans, status of dynamical systems, control and state variables. Some one's data output may be another person's data input, e.g., architectural plans. Data as programs, e.g., handloom cards.
Historical data: calendars, almanacs, awards of land, dictionaries. Revenue and agricultural data. Revenue maps. Geographic data-maps and timetables. Scientific data: tabulation of observations. Socio-economic data, e.g., census. Simulation and state space data, e.g, railway control rooms.

- Operations on data. It creation by observations, gathering or
ccomputations. Modification and transformations on data-sets. Its analysis, representation and display. Who gathers it and how does she gather it? Who modifies it, how often and to what extent? Who uses and why? Classifying the above data-sets by these attributes.
*Assignment*. Tabulating data-sets in terms of who, how and why. Each student to identify a new data set and tabulate. Data set obtained by sampling. Doing multi-criteria sampling. Simple linear regression model. Program to compute linear regression coefficients. Modelling (Household,member-height,member-weight) data-sets and classficiation of individuals and households as under-weight.- The presentation: How, who and why. pdf. Here is a collection of images of data sets, both modern and ancient that we will discuss in class. I will eventually add a 2 line description of all images. Images
- Thane district Census Dataset (2011, Part I) xlsx
- Assignment 1 text

**Module 2**. Review of Programming.

- File handling. Recursion:
`factorial`and the factorial problem. Inefficiency and efficiency. Presentation pdf. Programs: Factorial cpp and the An-Bn problem cpp. - Structs. Presentation pdf. Classes. Presentation pdf. Programs: Examples of structs and processing. Reading in student data cpp. Reading in from a file into an array of structs. cpp. The polynomial class cpp. Differentiation and the Newton Raphson methodcpp.
- Stacks. Basic operations.
- Queues. Presentation pdf. Array implementation.cpp. Linked lists and dynamic memory. Queues as a linked list. cpp. Sample input text. Priority Queues.
- Searching and sorting for structs with comparison. Presentation pdf.
- Time complexity. Order
*O*notation. Space complexity. Analysis of typical algorithms. Its use in analysing every algorithm henceforth. *Assignment*. Program to model the secretary problem as an array of stacks. Modifying Queues to allow for students to join behind their hostel-mates, or behind students from their hostel but junior to them. Polynomial division.*Optional Topic*. The Cowherds of Gokul. Presentation pdf. Srirang's code cpp and the bids text

**Module 3**. Basic Example 1 - Dictionary. Understanding a few practical examples, jpg. Preparing `struct` and `class` for these examples and preparing stubs for all functions. Writing out simple functions.

- The Dictionary. The attributes of an entry-word, root word, extensions, meaning, usage. Lexicography and the root-word problem (
*run*vs.*ran*). The basic operations. The*devanagiri*and chinese dictionary. - Characters and files. cpp. Strings and its operations. cpp. The empty string. cc. Blanks vs. non-blanks. Words. Storing words as strings, cpp, and input text. Comparing words. Locating words in text. The dictionary as an array. Preparing a dictionary entry as a
`struct`as it would appear. Searching a dictionary. Inserting an element. - Formatting text. Basic formatting. Code cpp and input text. Removing blanks. Left-alignment and left-right alignment in fixed width. Hyphenation.
*Assignment*. Next lexicographic word for a given word. Writing a left-right alignment algorithm with hyphenation.

**Module 4**. The Railway Timetable.

- The railway time table, jpg. The station list. The network. The organization of the rows of the page and the number of pages. A train and its attributes. Arranging the columns.
- Representing a network, jpg. Graphs. Adjacency matrix vs. sparse representations. Converting one representationinto another. Cycles, Paths and Trees. Connectedness. Spanning trees. Input/Output of graphs.
- Graph search,
*bfs*and connection with shortest paths. Defining and using dfs. Marking a vertex, hashing, modifying entries, copying vertex labels. Getting spanning trees out of a traversal. Duplicating graphs. Computing connected components. *Assignment*. Writing a program to duplicate a graph. Search on alternate graph representations with searching for labels. Watersheds of a vertex in a graph with node elevations.- Input/Output of stations, networks and trains. Compacting railway graph networks into
*section*graphs. Major and minor stations. Splitting a network into pages. Representing a train: Path and stoppages. Preparing a column. Ordering columns. *Assignment*. Merging and intersecting two increasing sequences. Verifying the non-overtaking condition for double-lines.

**Module 5**. Trees as data structures. Traversals. Search trees and priority queues.

**Module 6**. The Revenue Map and polygonal algebra.

- The revenue map. Types of objects-Plots, rivers and streams, wells, trees. Classification by use. Conservation of land and its modelling. The basic tables. Operations-breakup, join, change use.
*Assignment*. The GIS as a system. Listing data-types. Various operations. Operating a GIS model. Writing sample queries and creating new shape-files.- Points, segments, polylines and oriented polylines. Oriented polyline intersections. Polygons. Triangulating a polygon. Verification of polygon nature. Splitting a polygon by a polyline. Area and perimeter.
- Applications. Verifying a revenue map. Measuring irrigable area. Shortest path from well to plot.
*Assignment*. Polygons with holes. Adding vertices into polygons. Making two polygons compatible for joining. Joining two polygons. Managing components.

**Module 7**. Simulations.

**Module 8**. IRCTC

**Module 9**. Linkages with other courses.

Prof.milind 2016-12-18