ساختمان داده

ساعت 16-18 اين هفته مورخ 88/09/12 كلاس فوق‌العاده ساختمان داده‌ها برگزار مي‌شود.

در راستاي برنامه ريزي براي كلاس‌هاي آتي، با توجه به ساعات كلاسي دانشجويان كه آقاي صالحي تهيه كرده‌اند روزهاي شنبه و يك‌شنبه صبح ساعت 8-12 دانشجويان كلاس ندارند. بنابراين روز شنبه مورخ 88/09/21 ساعت 8-12 كلاس فوق‌العاده ديگري خواهيم داشت. افرادي كه در اين ساعت آن روز كلاس دارند هر چه سريعتر از طريق بخش نظرات اطلاع دهند.

تمرين پايگاه داده - آز پايگاه داده

با توجه به جداول صفحه 45 كتاب Silberschatz به سوالات زير پاسخ دهيد.

• چه مشترياني هيچ حسابي در هيچ بانكي ندارند.
• چه كساني حداقل شماره يك وام آنها يكي بيشتر از شماره يك حسابشان برابر شده است. (مثلا دارنده حساب شماره 100 وامي گرفته است كه شماره آن 101 است)
• چه كساني در يك شعبه بيش از يك حساب دارند.
• چه كساني تعداد وامهايي كه از كل شعبات گرفته اند بيشتر از تعداد حسابهاي آنها در يك شعبه است.
• كساني كه تمام وام‌هايي كه گرفته اند از شعبه آزادي بوده است در چه شهري زندگي مي‌كنند.
• چه كساني كه حداقل يك وام از شعبه اي گرفته اند كه در شهر خودشان است.
• كساني كه تمام حسابهايي كه دارند و تمام وام ‌هايي كه گرفته‌اند از شعبات شهر خودشان بوده است، آدرس شان چيست؟

با توجه به اينكه وقت زيادي براي حل تمرين‌ها نمانده است، تعداد تمرين كمي داده شده است.

تمرين پايگاه داده

query هاي زير را بنويسيد (جداول همان جداول كتاب هستند)
از دستور except، intersect نمي‌توانيد استفاده كنيد.

1. شعباتي كه هيچ مشتري اي ندارند مشخص كنيد.
2. شعباتي كه هيچ مشتري اي از شهر ديگري ندارند.
3. شعباتي كه يك مشتري دارند كه موجودي وي نصف موجودي كل آن شعبه است.
4. چه كسي در هر شعبه در كل بيشترين موجودي را دارد.
5. چه كساني وامي كه گرفته است از مبلغ موجودي اش بيشتر است
6. چه كساني مبلغ وام آنها از يك شعبه از كل موجودي يك شعبه ديگر بيشتر است.
7. چه شعبه اي بيشترين وام را داده است.
8. چه كساني بدون داشتن حساب، وام گرفته‌اند.
9. چه كساني شماره دو وام آنها دو عدد پشت سر هم شده است (مثلا شماره وام اول:100 و شماره وام دوم:101)
10. چه كساني حداقل شماره يك وام آنها با شماره يك حسابشان برابر شده است. (مثلا دارنده حساب شماره 100 وامي گرفته است كه شماره آن نيز 100 است)
11. كسي كه كل وامي كه تا به حال از يك شعبه دريافت كرده است، از همه بيشتر است، كل موجودي وي چقدر بوده است؟ شعبه اي كه از آن وام را دريافت كرده است كل موجودي آن چقدر است.
12. بيشتر مشتريان هر شعبه از چه شهري هستند.
13. چه شعباتي فقط به افرادي كه در همان شعبه حساب دارند وام داده است.
14. چه شعباتي به تمام افرادي كه در همان شعبه حساب دارند وام داده است.
15. اطلاعات مشتريان هر شعبه را نمايش دهيد (اين سوال هم واسه اينكه خستگي تون بره!)

تمرين‌ها روز پنج شنبه مورخ 88/09/05 تحويل گرفته مي‌شود.

كلاس فوق العاده

ساختمان داده:
كلاس فوق‌العاده روز چهارشنبه 88/09/04 ساعت 10-12 و ساعت 12-14 برگزار مي گردد. در اين ساعات ارائه روش‌هاي مرتب‌سازي مي‌باشد.
كوئيز روز سه‌شنبه 88/09/03 ساعت 14-16 برگزار مي‌شود. 5 سوال دارد و 2 ساعت فرصت. توجه كنيد كه برخي مسائل را در ساختمان داده بايد بدانيد؛ مثلا اينكه مربع جادويي چيست؛ چگونه حل مي‌شود يا maze چيست و حل آن چگونه است.

پايگاه داده:
كلاس خالي وجود ندارد! روز پنج‌شنبه ساعت 8-10 كلاس درس و ساعت 10-12 ارائه خواهيم داشت. دانشجوياني كه ارائه دارند بايد فايل‌هاي تكميل‌شده خود را براي من تا روز دوشنبه بفرستند.

دانشجويان ساختمان داده

كلاس فوق العاده همان طور كه گفته شد، دوشنبه مورخ 88/09/02 برگزار خواهد شد ساعت 8-12 و ارائه ها در آن تاريخ خواهد بود. كوئيز همان‌گونه كه روي برد دانشگاه نصب گرديده جمعه خواهد بود.

فايل‌هاي ارائه‌اي كه براي من فرستاده‌ايد مي‌توانند خيلي كامل‌تر باشند. سايت www.youtube.com خيلي فيلم‌هاي كوتاهي دارد كه مرتب سازي را نمايش مي‌دهد. كمي خلاقيت به خرج دهيد.
در مورد سوالات مرتبه زماني الگوريتم مي‌توانيد مراجع متنوعي را مطالعه كنيد. در مورد اكثر روش‌هاي مرتب‌سازي منابع زيادي وجود دارد، هم به زبان فارسي و هم به زبان انگليسي. چندين منبع را بخوانيد تا به فهم درستي برسيد.
سعي كنيد يك پياده‌سازي از الگوريتم را داشته باشيد؛ (مي‌توانيد از اينترنت پيدا كنيد)؛ برنامه‌اي كه اجرا كنيد و خروجي آن مرحله به مرحله، مراحل sort را نشان دهد.
حتما بيش از يك مثال در document خود داشته باشيد. توجه كنيد كه ارائه شما را بايد تمام دانشجويان متوجه شوند.

To All Students!

I was supposed to tell you about our make up class.
There is no vacant room on some hours in Wednesday. The time of the class also interfere with some other classes time or work hours of other students.
I really don't like to ignore even one student when arranging a time.
Tell me bout Mondays 88/09/02. Who has a serious problem on that day? Don't tell me about your preference please.
So probably we will not have any make up classes this week.
Any Comment? Tell me.

قوانين كلاس مهندسي نرم‌افزار

هر گروه فقط 15 دقيقه فرصت ارائه دارد. در اين 15 دقيقه مي‌تواند هر مطلبي را كه در مورد پروژه خود است عنوان نمايد؛ اما به نفع وي است كه از اين زمان حداكثر استفاده را بنمايد!
پس از هر ارائه 5 دقيقه فرصت پرسش و پاسخ است. در اين فرصت دانشجويان حق دارند سوالات خود را مطرح نمايند.
هر دانشجويي كه در حين ارائه يا در هنگام پرسش و پاسخ مطلبي را عنوان كند كه خارج از بحث مهندسي نرم‌افزار باشد و البته كه تشخيص آن با من است، به وي تذكر داده شده و 1 نمره از نمره پايان ترم وي كسر شده و بايد كلاس را ترك كند.

هدف از ارائه علاوه بر آشنايي با بحث هاي مهندسي نرم‌افزار، آشنايي با تحليل چندين سيستم مهم تجاري نيز مي‌باشد. سيستم‌هاي مالي، انبار و اموال، دبيرخانه و فروش سيستم‌هاي مهمي در دنياي كار كنوني ايران هستند.

مهندسي نرم افزار

مرسي بچه ها كه اكثريت نظراتتون رو برام فرستادين!! بعضي نظرات خيلي با هم متفاوت بودن!

فعلا كلاس رو از ديدگاه خودم بگم:
كلاس عاليه! دانشجويان فعالانه مطالعه مي‌كنن. مطالب رو بررسي و تحقيق مي‌كنن. از نتيجه تحقيقات كوئيز گرفته شده و مي‌دونم كه اون چندتايي كه به هر دليل تحقيق نكردن چه افرادي بودن.
من اگه هزاران حرف بزنم در زمينه انواع متدولوژي ها، هيچ وقت جاي اون كاري رو كه خودتون تحقيق كردين و سعي كردين بفهمين نمي‌گيره.
گروه‌ها دارن روي پروژه‌هاشون كار مي‌كنن. رقابت جنبه خارجي اش كه من مي‌بينم خوبه! خيلي شركت‌ها هستند كه واسه شركت ديگه مي‌زنن!! من خودم شركتي كه بودم از طرف اماكن اومدن و دو روز در شركت رو بستن!! مسئولان شركت مي‌دونستن كه فلان شركت اين كار رو كرده و باعث شده كه اين‌ها بيان. چقدر سختي كشيدن كه هيچ مشتري نفهمه شركت بسته شده اون هم از طرف اماكن!!

شماها هر كدوم قابليت‌هاي متفاوتي دارين، تيم‌هاي متفاوتي رو تشكيل دادين؛ و در آينده هم مشتريان متفاوتي رو مي‌تونين به سمت خودتون جلب كنين!! من سر كلاس هم گفتم كه گروهي كه اول ارائه كرد اگه قرار بود يه اداره دولتي معمولي قراردادي رو ببنده با اونها مي‌بست!!!
به نظر من تمام كلاس مفيد صرف مي‌شه، مفيد و مفيد و البته كاربردي. خود اين كلاس يه تجربه اوليه خيلي خوب شده كه من اصلا انتظارش رو نداشتم!!
يه بررسي بكنين ببينين كلاس‌هاي ديگه مهندسي نرم‌افزار چي مي‌گن؟! و چه قدر از مطالب گفته شده رو دانشجو درك مي‌كنه؟ من خودم نمره خيلي خوبي از اين درس گرفتم، خوندم و حفظ كردم و امتحان دادم، اما هيچي نمي دونستم!! گفتم كه حتي نمي دونستم چرا توي مرحله امكان سنجي هم بعضا پول دريافت مي‌شه!!!!!
انواع متدولوژي‌ها خيلي از اين‌ها بيشتره. ظاهرا انواع متدولوژي‌ها رو ياد مي‌گيرين اما در حين اون، انواع نگرش ها رو براي تحليل يك مسئله مي‌بينيم و اين‌ متدولوژي‌ها حداقل‌هايي هستند كه سر هر كلاسي بحث مي‌شه اما بعضا صرفا به صورت حفظي.

فكر نمره رو بگذارين كنار. من هزار و يك فاكتور واسه نمره‌دهي دارم؛ كار افراد رو مي‌فهمم؛ وضعيت گروه رو درك مي‌كنم.

ببينيد نگاه من با شما فرق داره. شما پيش داوري مي‌كنين كه چرا فلان گروه فلان مطلب رو سر كلاس عنوان كرده كه مي‌تونسته بيان نكنه؛ چرا گروه ديگه زودتر از كلاس اومده و اجازه خواسته و ارائه كرده. شايد هم پيش داوري نمي‌كنين و هم رو مي‌شناسين و مي‌بينين؛ و من نگاه مي‌كنم كه يه دانشجوي علاقمند مي‌خواد مطلبي رو واسه ديگران عنوان كنه و همه روش بحث كنيم. XP , RUP كه دوستاتون عنوان كردن همه كلاس هم در ارائه مشاركت داشتن و نظر دادن. خوب هم توضيح دادن، من هم توضيحات لازم رو در بين ارائه عنوان كردم. همه كلاس هم همه مطلب رو كاملا نمي‌دونست؛ از كوئيزها معلومه.

و اما
قبول دارم كه بايد قبل از ارائه هر گروهي، اين فرصت به ديگران هم داده بشه و كسي كه زودتر من رو ديده و از من اجازه گرفته نياد و ارائه بده و بقيه به جاي اينكه گوش كنن توي ذهنشون هي حرص بخورن كه جرا اين گروه اومده و و و و !!!!!
قبول دارم كه جلسه گذشته يه گروه خيلي صحبت كرد و به بقيه وقت نرسيد كه البته تاثيري روي نمره‌شون نداره اما بالاخره هر گروهي زحمت كشيده و بايد از شرايط مساوي بهره‌مند باشه تا حرف‌هاش رو بزنه.
قبول دارم كه كلاس كمي شلوغ شد و بحث‌هايي شد و جملاتي گفته شد كه بايد جلوي اونها گرفته مي‌شد.

قانوني واسه ارائه‌ها وضع مي‌كنم تا اين طور مشكلات حل بشه.

تمرين ساختمان داده

اين تمرين با يك مدل جديده!! چاره اي نيست. بايد ياد بگيرين كه اين جور تمرين‌ها رو هم بفهمين و حل كنين!! اين ها رو حل كنيد و جلسه آينده تحويل بدين.
حل تمرين‌ها رو زود شروع كنيد تا اگه اشكالي داشتين فرصت داشته باشين ايميلي از من بپرسين.

1. Design a O(N log N) algorithm to read in a list of words and print out all
anagrams.  For example, the strings "comedian" and "demoniac"
are anagrams of each other.

Assume there are N words and each word contains at most 20 letters.

Designing a O(N^2) algorithms should not be too difficult,
but getting it down to O(N log N) requires some cleverness.) 
________________________

2. Prove a lower bound for the following two problems:

2.1. You are given an array votes of size 4 with each element holding either a 1 or a 2 (which indicates the candidate for which a vote was cast). The goal is to determine if there is a candidate who received 3 or more votes. The output should either be the empty set if no candidate received at least 3 votes, or otherwise a set holding the indices in votes for a candidate with 3 or more votes.Consider a model of computation in which the algorithm can only access votes by asking if v[i] == v[j] for any i, j. You are to give the best lower bound you can on the number of comparisons.

2.2. You are given n coins identical in appearance; either all are genuine or exactly one is fake. It is unknown whether the fake coin is heavier or lighter than the genuine ones. Your model of computation to solve this problem is as follows. You can only learn about the coins through a provided weigh(set1,set2) method that takes as input two sets of coins set1 and set2 and returns one of the three possibilities:the two sets of coins have the same weight, set1 is heavier, or that set2 is heavier.The problem is to determine if any coin is fake, and if so which coin is fake and whether it is heavier or lighter than the genuine ones.
_________________________
3. Let L1, . . . ,Lr be r unsorted lists, whose elements hold integers in the range [0, k−1]. Let n be the total number of elements among all of the lists. That is, if ni is the number of elements in Li, then n = n1 + n2 + · · · + nr. Describe an algorithm with total worst-case asymptotic time complexity of O(r +k +n) for getting all of the r lists into sorted order. So your final output will be r sorted lists (containing L1,L2, . . . ,Lr in sorted order). Be sure to analyze the time complexity of your algorithm.
3-1. If you cannot think of an algorithm with the specified time complexity, then for partial credit describe the most efficient algorithm you can and correctly analyze its time complexity.
_________________________
4. Consider the problem of sorting an unsorted array A of n elements which take on only two different values (e.g. A = [37, 60, 37, 37, 60, 60, 60, 60]).Note that the two values are not known to the algorithm.
4-1. Briefly but clearly describe an O(n) comparison-based algorithm for solving this problem.
4.2. Why doesn’t the comparison sorting lower bound of (n log n) apply to this problem?

دانشجويان ساختمان داده

1. دو هفته پنج شنبه مورخ 88/08/28 كوئيزي از مباحثي كه از ابتداي سال تا آن تاريخ گفته خواهد شد، گرفته مي‌شود. اين كوئيز،2 نمره از امتحان پايان ترم را خواهد داشت.

2. جمعه همان هفته، مورخ 88/08/29 ساعت 8-10 و 10-12 صبح كلاس فوق العاده خواهيم داشت. در آن كلاس فوق العاده ارائه دانشجويان در خصوص روش‌هاي مرتب سازي صورت مي‌گيرد.
دانشجوياني كه در آن تاريخ كلاس دارند تا حداكثر دوشنبه مورخ 88/08/18 فرصت دارند كه به من اطلاع دهند.
تمامي دانشجوياني كه ارائه دارند لازم است حداكثر تا تاريخ 88/08/22 يك فايل word از مطالبي كه قصد ارائه آن را دارند، تهيه كرده و به من ارسال نمايند تا بررسي شود و اصلاحات لازم صورت گيرد. فايل word تكميل شده، پس از ارائه در اختيار ديگر دانشجويان قرار مي‌گيرد تا براي امتحان مطالعه نمايند.

3. هفته بعد از آن، مورخ 88/09/05 كوئيزي از مباحث فقط مرتب سازي گرفته خواهد شد كه اين كوئيز، 1نمره از امتحان پايان ترم را خواهد داشت.
_________________
توجه: پروژه تحقيقي خانم ابراهيمي و رحيم فرخاني درست تعيين نشده بود كه اصلاح گرديد.
توجه: سه روش مرتب سازي هنوز مانده است كه دانشجوياني كه تمايل به ارائه دارند، لازم است هرچه سريعتر اطلاع دهند. ارائه روش‌هاي مرتب سازي فقط در جلسه 88/08/29 خواهد بود.
_________________
توجه: كلاس جبراني جمعه به ساعت ديگري احتمالا سه شنبه مورخ 88/08/26 بعدازظهر موكول خواهد شد.
بهرحال، از نظر ارائه لازم است كه آماده باشيد. ساعت كلاس را تنظيم خواهم كرد.