Spring 2019, Zemoudeh
CSE 330: Data Structures
School of Computer Science and Engineering
California State University, San Bernardino


Last modified: Tues, May 28, 2019

Homework 4. Due Wed, Jun 5.
Write a program that decides whether a file contains balanced curly braces, parentheses, square brackets, and/or angled brackets. Input the file name, open it, and read one character at a time until end-of-file. If the file is balanced, your program should output "Balanced". If the file is not balanced, your program should output "Not Balanced". For example, the following files are balanced:

[()]{([])<>}

This is <((a))> {test} file
and [your] program should
[({o}ut)p{u}[t] ]<!>[] Balanced

#include <iostream>
using namespace std;
main()
{
    int a[100];
    a[20] = ((13 / 2) + a[5]) / 2;
    cout << a[20];
    cin >> a[20];
}

And the following files are not balanced:

This is { ( not ) 
a <balanced> file

neither is this
< > ] ( ) [ < >

{ ( not balanced } )

Use a stack of characters.

stack<char> brackets;
When an open bracket is read, it's pushed on stack. When a close bracket is read and its corresponding open bracket is on top of stack, the open bracket is popped.

Hand in a printout of your program and typescript of sample runs for each of the above input files.



Solution to Homework3: ui.cpp
Solution to Homework3 when input files include duplicates: ui_dup.cpp

Homework 3: Exercises 3.4 and 3.5 (117). Due Wed, May 22.

Write functions

template <class T>
list<T> my_intersect(const list<T> & a, const list<T> & b);
and
template <class T>
list<T> my_union(const list<T> & a, const list<T> & b);
to perform the intersection and union of lists a and b respectively. You may assume the lists do not include duplicates.

Implement the following algorithm.
1. In main() input the values for each list from its own file. The file names are lista and listb respectively.
2. Pass the lists to the desired function.
3. Copy the (constant) lists into temporary lists. Sort temporary copies (you may call generic sort()). Perform the operation (intersection or union) analogous to merge().
4. Return the resulting list to main() to be displayed.

Give your own main() to demonstrate the correctness of both functions.
For example, if file lista contained

this is a test file
and listb contained
this is another file
then the output for intersection is
file is this
and for union is
a another file is test this

Hand in a printout of your program and typescript of a sample run.
Don't forget to include the time complexity of each function in its header documentation.



Merge sort: mergesort.cpp

String.h String.cpp String class including substr() method.

Sequential and recursive versions of binary serach binarySearchSeq.cpp and binarySearchRec.cpp

Solution to Homework 1 list version
words.cpp

Midterm Exam: Mon, May 13.

Solution to Homework 1

Homework 2: String::substr(). Due Mon, May 6.

Add substr() member function to your String class from Lab 3. There are two forms of substr()
substr(int pos) returns substring of the invoking object from pos to the end
substr(int pos, int len) returns substring of the invoking object from pos with length len

Provide your own main() to test and illustrate the correctness of your functions.

Hand in copies of String.h, String.cpp, main.cpp, and typescript of a sample run.



Homework 1: Selection Problem. Due Wed, Apr 24.

Write a program to find the kth largest number among N numbers. You may assume 0 < k <= N.

Implement the following slow algorithm. (A better/faster algorithm is given in Ch. 7.)

The numbers are in an input file. Input value of k from the user. Read the first k numbers into an array and sort them into non-increasing order. Next, read the remaining numbers one by one (until end-of-file). As a new number is read, if it is smaller than the number in position k-1 in the array, it is ignored. Otherwise, it is placed in its correct position in the array, bumping out the number in position k-1. When all numbers are read, the number in position k-1 is the answer.

Hand in a printout of your program. Also hand in printout of a typescript of three sample runs for
(k = 1, N = 1)
(k = 1, N = 3)
(k = 3, N = 10)
and the corresponding input file in each case.



Figure 1.18 IntCell.cpp illustrates Big-Five/Big-Six.

Modulo.h Modulo.cpp Modulo_test.cpp illustrate operator overloading.

To be able to just type a.out to run a program (instead of ./a.out), add the two characters :. to the end of $PATH line in the file .bash_profile in your home directory.
In Linux . (dot) stands for current directory, and this adds current directory to search path. Now when you run a program, such as when you type a.out, the system will also look in the current directory and will find it.
.bash_profile runs when you first login, so this effect kicks in the next time you login. If you are too impatient and want to see the effect right away, manually run the file:
$ . .bash_profile


Add the following lines to .vimrc file in your home directory to automatically convert tabs to four spaces in vi (vim).
If .vimrc doesn't exist, create it.

" Only do this part when compiled with support for autocommands.
if has("autocmd")
    " Use filetype detection and file-based automatic indenting.
    filetype plugin indent on

    " Use actual tab chars in Makefiles.
    autocmd FileType make set tabstop=8 shiftwidth=8 softtabstop=0 noexpandtab
endif

" For everything else, use a tab width of 4 space chars.
set tabstop=4       " The width of a TAB is set to 4.
                    " Still it is a \t. It is just that
                    " Vim will interpret it to be having
                    " a width of 4.
set shiftwidth=4    " Indents will have a width of 4.
set softtabstop=4   " Sets the number of columns for a TAB.
set expandtab       " Expand TABs to spaces.



Fix all errors in the book from Errata List.

Follow the course Coding Style in all of your programming assignments and lab works.

Tutorials on PuTTY and WinSCP.

LABRATORIES

Lab 1: Infix-to-postfix Expression Conversion
Lab 2: Time Complexity
Lab 3: String
Lab 4: Vector
Lab 5: List Due date postponed to: Wed Lab May 15; Mon Lab May 20
Lab 6: Stack and Queue
Lab 7: Binary Search Tree
Lab 8: Set
Lab 9: Unordered_map
Lab 10: Priority_queue

Use this Lab Report Format to submit your reports.

You have one week, after first attending a lab, to hand in the Lab Report and email the source code to Mr. Thys Feenstra
(004861775@coyote.csusb.edu) course TA and lab assistant.

Email subject line must be "Last name, First name, CSE 330, Lab #".

Email only the SOURCE CODE. You must hand in a PRINTOUT OF LAB REPORT.

For example, Lab 1 Report is due Wednesday, Jan 17, sharp at 3:30 pm. Lab 2 Report is due Wednesday, Jan 24, sharp at 3:30 pm. And so on.

LATE LAB REPORTS WILL NOT BE ACCEPTED.



Syllabus