Raster Analyzer

Assignment 1 – August 24, 2005
Due: Friday, August 26, 2005
Language: Write this in C or C++.

Write a program to read in data points into a grid.
The data points should be bytes (characters).
Generate a 1-byte code for each element in the grid that indicates whether each of the 8 neighbors of any given element in the grid is equal to the current element. Your output will be a grid of values that has the same dimension as the original grid. Save the output to a file.

Create your own input data. Expect an example input file in binary form for the next version of this assignment.

Here’s an example simple input data file. You don’t have to use this method but it suggests a way if you can’t think of your own. The first line is the dimensions. Data follows. 

6 26
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxy
yzabcdefghijklmnopqrstuvwx
xyzabcdefghijklmnopqrstuvw
yzabcdefghijklmnopqrstuvwx
zabcdefghijklmnopqrstuvwxy

Do not assume that all characters are printable. In other words, values in your output grid may be anything from 0-255. For convenience during development you may use data of your own construction as input. A simple way to create this data is by using printable values.

An example of encoding the values for the byte codes is: Use the highest bit in the byte code for the element above and to the left (northwest) of the current. Use the next lower bit to indicate the neighbor immediately to the right (east) of the last and proceed through the neighbors in a clockwise fashion.

Along the edges of your grid you will have no neighbors. Assume that the empty neighbor elements are NOT equal to the current element.

Bring your code to discussion section on Friday at 9am. Location to be determined. Each student must present code to your classmates. If you have a laptop, bring it to use for your demo. If not, put code where you can get to it. Sometimes we will actually make changes and try them out in class.

First: show code that works even if it isn’t complete.
Second: show code that you’re working on.

Code Review – Roles and responsibilities

Moderator – distribute code to reviewers. Lead review. Make sure that notes from scribe from last review are considered in this week’s review.
Author – write the code, present in class, provide code to moderator or assigned reviewers in timely manner.
Reviewer – scrutinize code of author. Focus on either style or design. Ask questions of the author to further understanding of all in class.
Scribe – record changes suggested by reviewers or indicated by author.

Raster Analyzer - Optimized!

Assignment 2 - August 29, 2005
Due: Friday, September 2, 2005
Language: Write this in C or C++.

Objectives:
Modify the Raster Analyzer program from last week.
Optimize it using the methods described in class.

Read in the provided binary file. The header provides the number of rows and columns as 16-bit integers. Here is the description for the file header:

offset type description
0 16-bit int header length
2 16-bit int rows
4 16-bit int columns
6 16-bit int longitude of lower left corner
8 16-bit int latitude of lower left corner
File header description

A sample file is available here. This file is in little-endian binary format. So you would have to use an machine that has a x86 processor to read it for instance.
Time the main part of your executable from last week as discussed in class.
Time the main part of the new program and compare to "naive" solution.

On style:

Grading:

Understand Obfuscated C-Code

Assignment 3 - September 6, 2005
Due: Friday, September 9, 2005

For this assignment, you would need the recover.c file from here.

The assignment is to try to understand how the recovery program works and comment on style, comments, etc. Take a portion - say one function and re-write it in a way that is more clear. This may only be formatting the text so that it's more readable and adding comments. No one will be judged on syntax AT ALL. No one will be judged on the "correctness" of their comments or efforts to improve readability. If you see something that isn't clear, make a comment to that affect. If you THINK a line of code means something but you're not sure, make a comment and write a line that you think would be more clear to replace it.

What this program actually does: This program recovers the entire contents of a disk drive in FAT16 (a specific disk format that was once used by DOS and Windows) by making a BIOS call that gets each sector of the file and writing it to a new disk. It does this recursively, tracing through all directories and subdirectories.

Each entry in the directory tells whether an entry is a file or a directory and the location of the first sector of the file. There is a table entry (File allocation table or FAT) for each sector that tells where the next sector of the current file is. So if the first sector of the current file is 100, I could look in entry 100 and find the sector number of the next sector of the current file. I can repeat this until the next sector indicates that I should stop.

Grading will be on whether you made a presentation and whether you commented on the presentation of others. Be helpful if you can when speaking to others about their efforts.

Parsing Metadata for a "Programming Portfolio" with a Finite State Machine

Assignment 4 - September 12, 2005
Due: Friday, September 16, 2005
Language: Any programming language of your choice.

Objectives:

We mentioned that we will be asking you to produce a program portfolio, where prospective employers can get an overview all of your projects. This is the first of several assignments in which you will write a program that produces that portfolio. The input to this program will be a file containing information about your projects (a "metadata" file). The output will be one or more XHTML files that, together with the files named in the metadata file, will be the portfolio.

This metadata file includes information about each of your projects. The format of this file is specified in an attached file. Please right-click and choose Save As.. since viewing the .txt file in your browser will hide all the metadata tags. While you may add enhancements to the format, make sure that your program is still able to read in a metadata file specified in the original format.

You need to do the following:

  1. Read in a metadata file as input.
  2. Parse this file; the format is specifically designed to allow the use of a Finite State Machine for parsing and you should use one. Create an internal representation of the metadata.
  3. Generate XHTML files that present the information in the metadata file. There may be more than one XHTML file. The entry point for navigation through the portfolio should be named index.html. Note that the metadata includes the names of other files, such as source code files. These files should be linked from your portfolio page. Obviously, for the portfolio to be viewed, these files must also be in the directory containing the generated XHTML.

XHTML is just stricter HTML.

These XHTML files should offer a nice interface for browsing your projects. That is, you should be able to open the index.html file and browse to a page for any one of your projects, where you can see more detailed information and access the source code. The format and presentation of these files are up to you. You may make use of CSS or Javascript. For example, you could transform your metadata into the S5 format to convert them into a slide show.

Grading:

Note:

Parsing Your Own Metadata for a "Programming Portfolio"

Assignment 5 - September 19, 2005
Due: Friday, September 23, 2005
Language: Any programming language of your choice.

Objectives:

The instructions might be a little confusing, so please read them carefully and ask questions when in doubt.

Your portfolio generator currently generates XHTML that is hard coded for a specific set of known tags with known relations. You are now to extend the functionality of this application by moving much of the data and the definition of the finite state machine to be outside of your source code.

You will do this by:

  1. Read a file of your own design (the format file) that represents the relationship between legal tags. The format of this file is determined by you.
    • Example of the format that describes the metadata that we gave last week:
      portfolio: project
      project: title, date, author, summary, files, versionhistory
      date: day, month, year
      files: doc, code
      doc: f
      code: f
      versionhistory: version
      version: number, info
      How to interpret this data. This means that portfolio can only contain the project tag as a direct child. The project tag can contain title, date, author, summary, files and versionhistory tags. So this example of a format file tells us the tags that we can expect.
    If you know what a DTD for an XML file is, this is exactly the concept that we want to except that you do not need to use a DTD file. Creating an format file that specifies the list of tags and their hierarchy allows for new tags to be created and will allow that little code needs to be changed to handle those new tags.
  2. Read a file of your own design (the output format file) that we will used to describe how the different tags get mapped to different output tags. This will allow you to change the look of your portfolio without changing your source code.
    Our advice: do not do something like this: portfolio => h3. That is, this would replace all occurrences of portfolio with h3. This limits what you can do. For instance Latex does not necessarily have the same beginning and end tags. To write a document in Latex, it would look like \begin{document} Some text \end{document}
    • Example of something that you could use
      • portfolio:
        begin:
        end:
      project:
        begin: <h3>
        end: </h3>
      title:
        begin: <b>
        end: </b>
      ...
      ....
      ......
       In the above, portfolio was intentionally left without any begin or end tags.

Unfortunately, this may impact your design quite a bit and require significant re-writing. A sample format file, metadata file, output format file and output attached here. Right-click and Save As...

Grading:

Note:

Flattening water!

Assignment 6 - September 26, 2005
Due: Friday, September 30, 2005
Language: Any programming language of your choice

Objective:

You will be given a grid of integer values that represent elevations. We will be working with the same geographic area as before.

There will be values in the terrain attribute data (TAD) from the first assignment that map to various types of water. Since water is flat, you need to scan through the elevation data and flatten the terrain wherever water is indicated in the TAD file. Assume that "square" formed in the elevation data by a given post and the neighbors to the east, north and northeast need to be flattened whenever the TAD value is a water value.

Here is a suggested naive method:
Scan through the grid of TAD values, whenever there is a water value set the elevation of the 4 posts mentioned above to the lowest of the 4 values. This method entails making multiple passes.

This will be a two week assignment. Next week, we will want you to display the results in a graphical form. Sample skeleton code will be given that uses OpenGL and GLUT framework. You may also choose to use any other drawing APIS that you are familiar with.

You will use the TAD from Project 1. The file format remains the same as it was in Project 1. Remember that in the TAD, we have 256 x 256 grids. And of course, you need to know how water is represented. There are two types of water bodies that you need to care about: 0x52 is ocean and 0x41 is inland water.

Finally, you would also need the elevation file (binary file) from here. The data (that means each grid's elevation) consists of 32-bit integers. The header is 128 bytes. The number of rows and columns is at offset 24 bytes, both are 32-bits integers. In this particular implementation, there are 257 rows and 257 columns. The first 2 integers are 32-bit latitude and longitude but the units are 1000ths of a degree (but you do not need to care about this).

CAVEAT: The data in the TDA files are bytes! And the elevations are 32 bit integers.

Here is a picture that should make things clearer.

How the two raster files line up

The white grids are from the TAD file and the gray grids are from the elevation file. As you can see, in this example, there is an additional row and column of gray grids. However, notice that they line up at position (0,0). And that is how you should think of them. The first data that you read in from the file should correspond to position (0,0). The next would be at (0,1) and so on. So right now, the directions north, northeast and east should be intuitive.

Every connected body of water should have the same elevation. Notice the "square" of blue grids in the middle of the diagram. All of them should have the same elevation. But what if we have something like the top right corner where we have only one patch of water? Then you must just set the elevation data on its north, northeast and east gird to the level of the water even though there is no corresponding grids on the TAD file. Remember, we are changing values in the elevation file. We use the TAD file just to tell us whether a particular grid is ocean or inland water.

Questions to ponder:

Grading:

Flattening water! Part 2

Assignment 7 - September 26, 2005
Due: Friday, September 30, 2005
Language: Any programming language of your choice

Objectives:

As mentioned last week, this week you will create a program that displays a graphical view of the terrain and its elevation. To help you out, I have created a simple GLUT program that draws some lines on the screen. There are lots of comments in the file to help you get started. The sample code that I wrote is in C. And it requires the GLUT libraries. For instructions on how to set up GLUT using Visual Studio .NET, please refer to this site. You may obtain a copy of Visual Studio .NET 2003 from the university by following the instructions here.

Alternatively, you may elect to use any other framework of your choice as long as it accomplishes the minimum requirements of the assignment:

It should look something like this:

This is all you need, do not go to the original website and read their instructions. It will only confuse you.
The lines represent the different elevations. Think of it as looking down the map from front to back. Also, your line segments should have different color depending on the terrain type. This means that each individual line can have multiple colors. Choose appropriate colors based on the terrain as identified by the tad.h file in the given in the zip file below. Also, your lines do not need to be curves, but you are most certainly allowed to make use of curves (OpenGL has some built-in support for splines).

Also, for this assignment, we require you to start using a version control tool. Subversion is one example of this which you all should be familiar with. The instructions which I send last time would be helpful to get you started. However, this time, please create your own repository and do not pollute the one on https://opensvn.csie.org/uiuc_cs242/trunk. You may create a local repository (one that exists on your hdd) or create a new one online using any of the free hosting sites (OpenSVN is one fine example). For a quick start to creating your own repository, refer to this page from the Subversion book.

For those of you who have never used a version control tool before, a good rule of thumb on when to commit your changes would after you have written a function that works correctly. We would like to see at least 3 commits to the repository with decent comments.

Finally, here is the zip file of all the stuff that you need for this assignment. There are 5 elevation files there. You would still use the same TAD file that you have from last week but read in different elevation files for each. This might actually create some rather weird effects. Also, as mentioned last week, you should not code the name of the files; instead, make your program behave like an application and read in the file names (maybe from the command line).

Grading:

Allowing Comments on Your Portfolio

Assignment 8 - October 10, 2005
Due: Friday, October 14, 2005
Language: Any programming language of your choice

Objectives:

As alluded throughout the course, we are once again back to our portfolio project. So, by now you should have a static portfolio page that showcases the projects that you have done throughout this course. This time around, we want to expand on that and make the page less static: by enabling comments.

For examples of threaded comments, please visit slashdot.org. All that we require is that we can reply to comments. That means there is some hierarchy to the comments. If you want, you can also implement sorting by date, comment score, etc.

While the description of the project is simple enough, your main hassle would be dealing with PHP and MySQL (or whatever language or database of your choice). Why? Here are a list of things that you need to keep in mind as you approach this:

As you can see, you need to make some design decisions. Deleting comments would be the thing you should worry most since it can lead to missing dependency issues. And do not say that you would not delete comments. There will be some that you want to delete. In the database class that I took, designing the schema of the database is really important because it can be extremely hard to migrate data from one schema to another.

Some technologies that you might be interested in trying out:

Nicholas: I have books for Ruby on Rails and AJAX. You may loan them from me.

Next week you will enable filtering for the comments. That way, no one can insert malicious html or javascript that can break your page layout.

Grading:

Allowing Comments on Your Portfolio - Part 2

Assignment 9 - October 17, 2005
Due: Friday, October 21, 2005
Language: Any programming language of your choice

Objectives:

As alluded throughout the course, we are once again back to our portfolio project. So, by now you should a page that supports some simple form of comments.

However, no one has implemented a filter system for profane terms yet. So, the next step would obviously be to include one. You can make this as elaborate as you like. For instance, you might replace the profane terms with their euphemisms. Or you can just replace parts of them with * for the vowels. Or, you could always do so with more creative ideas. Surf around the web and see how other people have been doing it.

Moreover, it would also be prudent to implement some kind of javascript and html filter so that comments will not break your page layout. There might already be functions to do this in your particular language so do check them out before writing your own version. If you find that your implementation might be more robust, then by all means, write your own.

And since you have an almost complete portfolio online, you would also want an admin page for it. You would want a page where you can quickly view all new comments that have been left. Also, you want to be able to delete comments as well. Additionally, you might want to be able to keep track of frequent viewers to your page based on their IP address, etc.

More importantly, we would also like to see all the projects that we have done so far included in your portfolio.

We want to have more questions and comments during the discussion section. Some guidelines for questions were given in the e-mail that the TA sent out last week. You will also find relevant checklists in Code Complete 2 chapters 31 and 32. Use those as guidelines to help you ask questions. An additional hint: ask the rest how they solved a particular problem that you were having. For instance, if you were having a hard time getting the filtering to work because they might be so many cases to consider, ask them how they did theirs.

This week's assignment is easier to give you ample time to prepare for the next one. In the next assignment, you would have to work with the students in your discussion section to come up with a simple graphics editing program. This would be a form of pair programming where you CANNOT write code unless everyone of your group member is there. This would be an enlightening experience for everyone.

Grading:

Image Editor

Assignment 10 - October 17, 2005
Due: Friday, October 28, 2005
Language: Any programming language of your choice

Objectives:

Pair Programming:

TWO programmers working side-by-side, collaborating on the same design, algorithm, code or test. One programmer, the driver, has control of the keyboard/mouse and actively implements the program. The other programmer, the observer, continuously observes the work of the driver to identify tactical (syntactic, spelling, etc.) defects and also thinks strategically about the direction of the work. On demand, the two programmers can brainstorm any challenging problem. Because the two programmers periodically switch roles, they work together as equals to develop software.
-- Laurie Williams
North Carolina State University Computer Science

For this assignment you will pair up with students from your discussion section. Since the afternoon section has 3 students, they will, instead, practice "trio programming". Your group will be in-charge of setting meeting times, project goals, etc that will enable you to succeed in this project.

You will implement a picture editor that is capable, but not limited, to the following features:

This assignment requires not only individual contributions but also group contributions as well. We have released this assignment earlier so that you get a chance to work out suitable meeting times with your group members. Do not worry if you cannot get everything done by the deadline. Show us a working version of what you have accomplished.

While you are free to use any language or framework that you choose, we suggest taking a look at Java and the facilities that it provides. Also, the Java language is one of the languages where it would be simpler to do Pair Programming in since everyone can install the JDK. Here are some links:

Hints:

Grading:

Image Editor Part 2

Assignment 11 - October 31, 2005
Due: Friday, November 4, 2005
Language: Any programming language of your choice

Objectives:

Everyone did a good job last week on their projects. We were so impressed that we decided to extend this project by one more week to see what else you guys can come up with.

Also, since most of you are already familiar with your code and the framework, this would also be a good opportunity to see if you would have any added benefits from pair programming.

We only ask that you implement the undo/redo functionality. You may choose to enable multiple redo/undo levels. Or you may just choose to redo/undo the last action. Of course, if you had any problems with your project last week, now is also the time to fix those minor annoyances.

For people using Java, you might want to take a look at the Java UndoManager. Here is an example on how to use it.

For people using another framework, an easy way to do this would be just to store the last image that the user sees and restore that whenever an undo action is requested. Of course, this is only limited to actions that actually modify the image, not something such as zooming in or out.

For the more ambitious, the best-practice way to implement undo/redo functionality is using the Command pattern. An example of how to do it in Java can be found here.

Final Project

Assignment 12 - November 7, 2005
Due: Friday, December 9, 2005
Language: Any programming language of your choice

You will work on a project of your choice within the 4 week time period. Each week you will present your progress in class. You will be evaluated on what you have accomplished for each week.

Since this is your project, you should be enthusiastic about your code and presentation. You should present in a manner that convinces everyone about why your project is a worthwhile endeavor. We will be looking out for the usual suspects in your code:

Also, looking at the lecture slides for November 7 will help you focus on what your program is supposed to do. It is very easy to off track from the original purpose of your program so be sure to review that you are doing frequently.

Post questions, concerns and comments to the class newsgroup at class.cs242