SE250:May 26

SOFTENG 250 class meeting for 26th May 2008

• Post topics that you would like John Hamer to discuss about the HTTB

Content of HTTB

• How can we make sure that the things we research for the HTTB is of use and is needed by the students for this course?

Minutes

Minute taker: User:tlou006

Minutes

Tradeoffs

There is no one “best” data structure to use

Hashing generally is good – fast – works for most data types – can make different hash functions

Sometimes things are not so clear cut

eg. Linked Lists vs Array lists

“cost” for operating at the front of the list, sometimes this cost can be removed – cost increases as list grows.

Memory overhead imposed with LL. If list is short then LL is small: one cell, but AL you have to make a big lump, like you are expecting more values.

Naive search methods – breadth-first, depth-first = brute force/naive: doesnt care much about our problem.

Smart search methods = knows a little about our problem and can make search more efficient – but more program costs

If AL, is it worth it keeping stuff in sorted order? when the data is in sorted order looking things up is faster, but inserting stuff is slower because you have to resort

Question regarding HTTB marks

Contribution is relative, not going compare with last year Expected workload is 10hours per week – after lectures and labs it is 4hours each week to do stuff, including HTTB

Don’t copy paste from previous HTTB

Something to a polished level of presentation, in depth

Screencasts better than wall of text, concise detailed, visual

Lectures end on 6th june, everything is done by then according to university standards, but ok to have extra dribble in after in the week

By the 6th you need to send to john a summary of your contributions to HTTB, he will give some feedback

Exam is on 16th

Focus on screencasts

Cover stuff beyond the course material but don’t overdo and overextend, mention important connections to other resources

Focus on stuff covered in labs

Hashing will come up in exam because its good topic

Hashing

In last year exam,

Hashing a New data type (hashing existing data type, eg. int or char is too easy)

When you have a key that is composed of various parts, there is no built in hashing function that hashes your data type, which is made up of strings and integers

We are given the hash function for strings, ints

1. hash each part

Combine the hash values together eg. Hash a deal hand of 5 cards eg. 52cards in deck 52 integers hashing

Does the order of the cards matter?? 12345 = flush 13425 != flush, the order of cards in the hand doesnt change the value of the hand

If order matter then combine asymmetrically

If not the combine symmetrically

Question regarding exams

Some stuff from last year exam will “echo” in this year

Mark’s section is multichoice

Exam format is the same-ish as last year(john threw in some hard questions for this year Q__Q,

some questions will be new from previous years, new ideas

The implications of topics, understand tradeoff issues

Will be asked to write a hash functions, write code for it

120 marks around 1minute a mark

3hour exam, should be done in 2hour so we not stressed :D

50/70 john/mark split

One on pointers,

One on pointers and arraylists together

One on hashing

Planning

• dcho040 : I'm going to make a screen cast to show the differences between 4 different data structures(LinkList, ArrayList, BinarySearchTree,HashTable). It will be a quite detail and I hope it will be uploaded today (6/6)