2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
The Four Programs
Introduc on
In this class, you will get a chance to try out a variety of programming languages. To help you appreciate the differences between these languages, you will implement the same set of programs in each language. These are referred to as ¡°the four programs¡± (creative, right?) The four programs are:
1. Implement Quicksort 2. Matrix Multiplication 3. Grade Report
4. Auto Advisor
These tasks were selected because they reveal a lot about the languages in which you implement them. For example, a language that does not support recursion makes implementing quicksort rather challenging (though not impossible.) Likewise, lack of good data aggregation will make the grade report task difficult. As you progress through the languages, you will find many situations in which the language either helps or hinders your ability to write the programs. Rest assured that any language can implement any program. The only question is how much support the language will provide to the programmer.
Grading
In general, the programs will be weighted evenly for each language. However, I will count your succesful programs as the ones with the most points. That is, I am going to rig the game in your favor by awarding a few more points to your best work. If you find that you cannot make a program work in a language, make your best effort and then write a bit about why it was a difficult task. I will reward your efforts with most of the points. The point here is to explore, not to become adept at any one language.
Details
Now that the preliminary instructions are in hand, this section will detail the functionality of each of the four programs. Here you will find sample runs, data files, and other such material.
Implement Quicksort
This program should prompt the user for 10 integers, which it will store in some appropriate container. It will then sort the list of integers using an implementation of quicksort. If you are not familiar with this algorithm, all you need do is head to the font of wisdom (http://wikipedia.org) where you will find a very nice article on the algorithm. I recommend implementing a simple
https://semo.instructure.com/courses/526/pages/the-four-programs 1/9
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
partitioning scheme, such as Hoare¡¯s original scheme. At any rate, for full credit the sorting algorithm must be implemented by you, and it must be quick sort. No other algorithm will do!
A sample run of the quick sort program is shown below:
Enter 10 Integers
0
-1
5
7
2 21 -3 4
8 100
Sorted -3
-1
0
2
4
5
7
8 21 100
Exciting stuff! Now on to something a bit more fun.
Matrix Mul plica on
Matrices are two dimensional arrays of numbers. Matrix dimension are typically listed in row, column order as are their indices. An m ¡Á p matrix has m rows and p columns. Two matrices can be multiplied if their inner dimensions match. That is, if matrix A has dimensions m ¡Á p, and matrix B has dimensions p ¡Á q then the result of their multiplication will have dimension m ¡Á q. If the number of columns in A does not match the number of rows in B, the matrices cannot be multiplied.
The multiplication itself is a combination of multiplication and addition. The simplest way to accomplish this multiplication is via an O(n3) algorithm as shown:
C = new matrix of size A.rows, B.columns
Set all entries in C to zero
For i = 1 to A.rows
For j = 1 to B.columns
For k = 1 to B.rows
C[i,j] = C[i,j] + A[i,k] * B[k,j]
End For
End For
End For
https://semo.instructure.com/courses/526/pages/the-four-programs 2/9
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
Note that the above assumes that the for loops include both the beginning and end of their range, and that the arrays have an index beginning at 1 (as is standard mathematics notation). Also C[i,j] refers to the entry at row i column j in matrix C.
Your program should ask for the dimensions of A followed by the variables in A. It should then follow suit for B. If the two arrays are not compatible, your program should indicate that they cannot be multiplied. Otherwise it should carry out the multiplication.
The first example run is of two incompatible matrices:
Matrix A ======== Rows: 2 Cols: 2 Values: 12
34
Matrix B
========
Rows: 3
Cols: 1
Values:
1
2 3
Incompatible Dimensions
And here is a run with compatible matrices:
Matrix A ======== Rows: 2 Cols: 2 Values: 12
34
Matrix B ======== Rows: 2 Cols: 3 Values: 12 0 03 4
Ax B= 188 3 18 16
Note that for the final display, you can do something simple like put tabs in between the numbers. Make it look as neat as possible, but I will not be counting spaces in between for exactness. Note that your matrices should allow for floating point values.
https://semo.instructure.com/courses/526/pages/the-four-programs 3/9
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
Grade Report
This is a program designed to hit you where you live! This program will compute your current average in a class, the minimum average that you could earn from this point forward, and the maximum average that you can earn. In addition to this, it prints the relative weights of each assignment category.
This program assumes that grades are computed out a fixed pool of points. For example, the course in which you currently find yourself has 1000 points. Your final average is computed by the formula:
grade = (points_earned * 100) / points_possible
So at any given point in the semester, you could compute your current average by totaling the points you have earned and dividing by the possible points on your assignments so far.
The minimum grade is what you would earn if you stopped handing in work. That is, you would forfeit all remaining possible points in the semester (not a good idea, usually!)
The maximum grade is what you would earn if you earned all remaining possible points in the semester.
This program will take as its input the name of a file. The file is a flat-format file of the following form:
1. The total number of points for the entire semester on a line by itself.
2. Zero or more assignment records, with each field being a fixed width. The format of these
records are as follows:
Assignment Name (20 characters) Category (20 characters)
Possible Points (14 characters) Earned Points (14 characters)
Consider the file generated by a student whom we will call ¡°Bill¡±. Bill has recorded his first few assignments in CS390 as shown:
1000
MS 1 – Join Grps
Four Programs
Quiz 1
FORTRAN
Quiz 2
HW 1 – Looplang
Group Project
Programming
Quizzes
Programming
Quizzes
Homework
5 5
15 9
10 7
25 18
10 9
20 15
Note that there is no separator between these fields! If they use the full width of the field, they run right up to the next one:
HW 3 – Struct & VarsHomework 20 20
https://semo.instructure.com/courses/526/pages/the-four-programs 4/9
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
When Bill runs the program, it generates the following output:
File: Bill
Group Project (5%)
==================================
MS 1 – Join Grps 5/5 100%
==================================
5/5 100%
Homework (23%)
==================================
HW 1 – Looplang 15/20 75%
==================================
15/20 75%
Programming (47%)
==================================
Four Programs 9/15 60%
FORTRAN 18/25 72%
==================================
27/40 67%
Quizzes (23%)
==================================
Quiz 1 7/10 70%
Quiz 2 9/10 90%
==================================
16/20 80%
Current Grade: 74%
Minimum Final Grade: 6%
Maximum Final Grade: 97%
Here, neatness counts! Make the output line up in nice neat tables. Also note that category weights are the weight of how much the category counts toward the current average. At the end of the course, these would match the weights in the syllabus. Also, note that while Bill is earning a C, if he buckles down he can still get that A. Perhaps you could use this program to help you in your courses!
Sample Data Files
Here are a couple of sample data files for this program. You will want to make some files of your own to really test your code!
bill (https://semo.instructure.com/courses/526/files/33762/download?wrap=1) cs390-assignments (https://semo.instructure.com/courses/526/files/33763/download?wrap=1)
Auto Advisor
Many a job has fallen to the mighty forces of automation! In fact, I could tell you harrowing tales of when my own code has ousted entire departments of workers. Well, I am not immune to such
https://semo.instructure.com/courses/526/pages/the-four-programs 5/9
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
https://semo.instructure.com/courses/526/pages/the-four-programs /9
things. In this section, you will automate one of my several job functions. You will create a program which can advise students about their overall academic performance, and make recommendations about what courses they can take next.
To support this, we will create a data file for each student based on their major. The format of this file has each required course or category organized into records. There is one record per line, and they are delimited with ¡°|¡± symbols. The format of these records are shown below:
Course/Category | Credit Hours | Prerequisites | Grade
These fields can have any number of characters, and the trailing or leading spaces of the fields are ignored. The course/category field is free-form and consist of any combination of characters other than a ¡°|¡± or ¡°,¡±. The credit hours is the number of hours in the course/category. The grade is a single letter. A blank grade entry indicates a course has not been attempted, an F means it has been failed, and any other letter means it has been completed.
The prerequisites are listed in a comma separated list where the entries match the Course/Category of another record. A comma separated list are requirements which undergo an ¡°and¡± operation. For example, consider the following course:
CS380|3|CS288,CS351|
This entry indicates that CS380 is 3 credit hours long, has not been attempted, and prior to taking this course a student must complete CS288 and CS351.
Individual lists of courses can be separated by spaces to indicate an ¡°or¡± operation. Take for instance the following:
CS591|3|CS300,CS380,CS480 CS300,CS503 CS500,CS503|
Here, CS591 requires one of the following conditions to be met: 1. CS300 and CS380 and CS480 2. CS300 and CS503 3. CS500 and CS503
Putting all this together, the complete requirements to earn a bachelor of science degree in Computer Science at SEMO is:
CS101|3||
CS155|4|CS101|
CS245|3|CS101|
CS265|4|CS155|
CS288|4|CS245|
CS300|3|CS265|
CS345|3|CS245|
CS350|3|CS300,CS345|
CS351|4|CS155|
CS380|3|CS288,CS351|
CS390|3|CS300|
CS433|3|CS300|
CS440|3|CS265|
CS445|3|Senior Standing|
6
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
https://semo.instructure.com/courses/526/pages/the-four-programs
7/9
Note that some things on this list are not courses! They include categories, which will be replaced my classes as the student progresses. They also include entries such as ¡°Senior Standing¡± and ¡°ACT24¡±, which are still conditions that can satisfy a requirement but are not really courses. These are listed with a 0 credit hour designation so that they can still work as prerequisites but will not be included in the computation of GPA.
So then, here is what the program does. It reads in a file and then prints out the following: 1. The overall GPA of the student, using the standard scale (A=4, B=3, C=2, D=1, F=0) 2. The number of credit hours attempted. 3. The number of credit hours completed. 4. The number of credit hours remaining in the student¡¯s degree. 5. A list of courses which the student needs, and which can be taken given the records already in place.
For example, say we took the above file and ran it. This would be the state of affairs for an incoming freshman. The program¡¯s output would be as follows:
CS480|3|CS351|
CS495|1|CS445|
CS499|3|CS445|
CS591|3|CS300,CS380,CS480 CS300,CS503 CS500,CS503|
CY201|4|CS155|
IU315|3||
MA139|3|ACT24 MA116 MA137|
MA223|3|ACT24 MA116|
MA464|3|MA223 MA250 MA338 MA345 MA443|
CS3xx+|6||
Science|9||
Social and Behavioral Sciences|6||
Constitution Requirement|3||
Written Communication|6||
Oral Communication|3|
Natural Sciences|7||
Mathematics|3||
Humanities and Fine Arts|9||
Additional Requirements|5||
Senior Standing|0||
ACT24|0||
File: csmajor
GPA: 0.0
Hours Attempted: 0
Hours Completed: 0
Credits Remaining: 126
Possible Courses to Take Next
CS101
IU315
CS3xx+
Science
Social and Behavioral Sciences
Constitution Requirement
Written Communication
Oral Communication
Natural Sciences
Mathematics
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
https://semo.instructure.com/courses/526/pages/the-four-programs
8/9
Of course, some of those are not classes, and perhaps that is where I can find my job security. (That is, I will still be useful to tell students that they cannot sign up for a better ACT grade!)
Now, suppose we ran this on a senior, one who had completed all their course work. One possible outcome would be something like this:
File: senior
GPA: 3.5
Hours Attempted: 128
Hours Completed: 128
Credits Remaining: 0
Possible Courses to Take Next
None – Congratulations!
Finally, let¡¯s suppose that we have a file of a typical rising sophomore. It may look something like this:
Humanities and Fine Arts
Additional Requirements
Senior Standing
ACT24
CS101|3||A
CS155|4|CS101|A
CS245|3|CS101|B
CS265|4|CS155|
CS288|4|CS245|
CS300|3|CS265|
CS345|3|CS245|
CS350|3|CS300,CS345|
CS351|4|CS155|
CS380|3|CS288,CS351|
CS390|3|CS300|
CS433|3|CS300|
CS440|3|CS265|
CS445|3|Senior Standing|
CS480|3|CS351|
CS495|1|CS445|
CS499|3|CS445|
CS591|3|CS300,CS380,CS480 CS300,CS503 CS500,CS503|
CY201|4|CS155|
IU315|3||A
MA139|3|ACT24 MA116 MA137|A
MA223|3|ACT24 MA116|
MA464|3|MA223 MA250 MA338 MA345 MA443|
CS3xx+|6||
Science|9||
Social and Behavioral Sciences|6||
PS103|3||B
Written Communication|3||
EN100|3||B
SP104|3||B
Natural Sciences|7||
Humanities and Fine Arts|6||
2020/10/26 The Four Programs: Fall 2020 CS390-01 Programming Language 12332
https://semo.instructure.com/courses/526/pages/the-four-programs 9/9
This would yield the following run:
File: sophomore
GPA: 3.42
Hours Attempted: 31
Hours Completed: 31
Credits Remaining: 92
Possible Courses to Take Next
CS265
CS288
CS345
CS351
CY201
CS3xx+
Science
Social and Behavioral Sciences
Written Communications
Natural Sciences
Humanities and Fine Arts
Additional Requirements
Senior Standing
ACT24
Sample Data Files
csmajor (https://semo.instructure.com/courses/526/files/35095/download?wrap=1) sophomore (https://semo.instructure.com/courses/526/files/33766/download?wrap=1)
Closing Remarks
In all of the four programs, you can assume that the input is correct. You do not need to provide any sort of error checking. As mentioned before, if you fail at a task, simply document why and submit your best attempt.
Good luck, and enjoy!
AR104|3||C
Additional Requirements|2||
UI100|3||A
Senior Standing|0||
ACT24|0||