算法設(shè)計(jì)與分析 實(shí)驗(yàn)教學(xué)大綱

PAGE2 算法設(shè)計(jì)與分析實(shí)驗(yàn)大綱 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程大綱 PAGE3《算法設(shè)計(jì)與分析實(shí)驗(yàn)》課程教學(xué)大綱課程代碼：****課程負(fù)責(zé)人：****課程中文名稱：算法設(shè)計(jì)與分析實(shí)驗(yàn)課程英文名稱：Algorithmdesignandanalysisexperiment課程類別：必修課程學(xué)分?jǐn)?shù)：0.5課程學(xué)時(shí)數(shù)：15～21授課對(duì)象：計(jì)算機(jī)科學(xué)與技術(shù)及相關(guān)專業(yè)本科本課程的前導(dǎo)課程：C/C++程序設(shè)計(jì)、離散數(shù)學(xué)、算法設(shè)計(jì)與分析一、教學(xué)介紹算法設(shè)計(jì)與分析實(shí)驗(yàn)是算法設(shè)計(jì)與分析的配套課程，主要通過上機(jī)編程鞏固算法設(shè)計(jì)與分析的基本原理和方法，掌握數(shù)據(jù)組織和算法設(shè)計(jì)和實(shí)現(xiàn)技術(shù)，培養(yǎng)綜合運(yùn)用算法設(shè)計(jì)與分析策略高效解決問題的能力。主要窮舉法、歸納法、迭代法和遞歸法等基本算法設(shè)計(jì)方法以及分治法、蠻力法、回溯法、分支限界法、貪心法和動(dòng)態(tài)規(guī)劃法等算法設(shè)計(jì)策略。二、教學(xué)目的算法設(shè)計(jì)與分析實(shí)驗(yàn)課程的總目標(biāo)是培養(yǎng)學(xué)生能夠根據(jù)需要開展實(shí)驗(yàn)研究，正確地描述數(shù)據(jù)和組織數(shù)據(jù)，并應(yīng)用數(shù)據(jù)處理方法，編寫程序，分析實(shí)驗(yàn)結(jié)果以獲得合理有效的結(jié)論，具備解決復(fù)雜工程問題的能力。算法設(shè)計(jì)與分析實(shí)驗(yàn)分為單機(jī)實(shí)驗(yàn)和在線編程。單機(jī)實(shí)驗(yàn)是在自己計(jì)算機(jī)或者實(shí)驗(yàn)室計(jì)算機(jī)上完成，目的讓學(xué)生領(lǐng)會(huì)算法的原理、驗(yàn)證算法的正確性和采用常用的算法策略求解問題。在線編程實(shí)驗(yàn)是在LeetCode、POJ或者HDU在線編程平臺(tái)中完成，目的是培養(yǎng)學(xué)生研究問題、合理地選擇數(shù)據(jù)結(jié)構(gòu)和算法策略構(gòu)建解決方案，并分析比較各種方案優(yōu)劣的能力。三、實(shí)驗(yàn)基本要求與方式1、基本要求課前：要求任課教師布置好實(shí)驗(yàn)題目、實(shí)驗(yàn)要求和實(shí)驗(yàn)?zāi)康?，要求?shí)驗(yàn)教師為實(shí)驗(yàn)準(zhǔn)備好必須的設(shè)備和軟件；要求學(xué)生提前編寫完成實(shí)驗(yàn)要求的程序代碼。課中：要求任課教師隨時(shí)解答學(xué)生提出的實(shí)驗(yàn)問題，同時(shí)要注重啟發(fā)和引導(dǎo)學(xué)生，使學(xué)生養(yǎng)成獨(dú)立思考、解決問題的能力，檢查學(xué)生的實(shí)驗(yàn)內(nèi)容；實(shí)驗(yàn)教師要及時(shí)解決實(shí)驗(yàn)設(shè)備可能出現(xiàn)的故障，保證實(shí)驗(yàn)順利地進(jìn)行。學(xué)生則應(yīng)該按照實(shí)驗(yàn)要求，認(rèn)真編寫和調(diào)試源代碼，完成實(shí)驗(yàn)內(nèi)容。課后：提交實(shí)驗(yàn)報(bào)告。2、實(shí)驗(yàn)方式單機(jī)實(shí)驗(yàn)題：輸入相應(yīng)的數(shù)據(jù)，通過檢測(cè)輸出結(jié)果，驗(yàn)證是否實(shí)現(xiàn)了實(shí)驗(yàn)的要求。在線編程題：在在線編程平臺(tái)提交代碼，查看提交結(jié)果，分析代碼運(yùn)行的時(shí)間和空間。四、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告按學(xué)院要求格式書寫，包含封面（含學(xué)號(hào)，姓名等），目錄，每個(gè)實(shí)驗(yàn)的題目，解答思路，程序框架，源代碼，提交結(jié)果圖（在線編程題給出包含提交通過、運(yùn)行時(shí)間和空間的截屏圖），實(shí)驗(yàn)體會(huì)（選）。五、實(shí)驗(yàn)內(nèi)容與學(xué)時(shí)分配說明：所有實(shí)驗(yàn)題的題目描述見《教材》，在線編程實(shí)驗(yàn)題目見LeetCode（）、北京大學(xué)POJ和杭州電子科技大學(xué)HUD網(wǎng)站。實(shí)驗(yàn)1：常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用學(xué)時(shí)數(shù)：0～3。任課教師根據(jù)學(xué)生情況在以下各種類型的實(shí)驗(yàn)題目中選擇若干實(shí)驗(yàn)題目。1.單機(jī)實(shí)驗(yàn)題（1）高效地插入、刪除和查找（2）一種特殊的隊(duì)列（3）方塊操作2.在線編程題（1）LeetCode328—奇偶鏈表（2）LeetCode394—字符串解碼（3）LeetCode215—數(shù)組中的第k個(gè)最大元素（4）HDU1280—前m大的數(shù)（5）POJ2236—無線網(wǎng)絡(luò)實(shí)驗(yàn)2：基本算法設(shè)計(jì)方法學(xué)時(shí)數(shù)：0～3。任課教師根據(jù)學(xué)生情況在以下各種類型的實(shí)驗(yàn)題目中選擇若干實(shí)驗(yàn)題目。1.單機(jī)實(shí)驗(yàn)題（1）最長重復(fù)子串（2）求子矩陣元素和（3）求n階螺旋矩陣（4）驗(yàn)證梵塔問題2.在線編程題（1）LeetCode344—反轉(zhuǎn)字符串（2）LeetCode206—反轉(zhuǎn)鏈表（3）LeetCode24—兩兩交換鏈表中的結(jié)點(diǎn)（4）LeetCode62—不同路徑（5）HDU1003—最大子序列和（6）HDU1143—三平鋪問題（7）POJ2231—奶牛的總音量（8）POJ1050—最大子矩形實(shí)驗(yàn)3：分治法學(xué)時(shí)數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實(shí)驗(yàn)題目中選擇若干實(shí)驗(yàn)題目。1.單機(jī)實(shí)驗(yàn)題（1）將一個(gè)整數(shù)數(shù)組劃分為兩個(gè)和差最大的子數(shù)組（2）四路歸并排序（3）查找假幣問題（4）求眾數(shù)（5）求漢諾塔Ⅱ（6）求Fibonacci數(shù)列2.在線編程題（1）LeetCode240—搜索二維矩陣II（2）LeetCode35—搜索插入位置（3）LeetCode33—搜索旋轉(zhuǎn)排序數(shù)組（4）LeetCode162—尋找峰值（5）HDU2141—能否找到X（6）HDU2199—解方程（7）HDU1040—排序（8）HDU1157—求中位數(shù)（9）HDU1007—套圈游戲（10）POJ2255—由二叉樹中序和先序序列產(chǎn)生后序序列（11）POJ1854—轉(zhuǎn)換為回文的交換次數(shù)（12）POJ1995—求表達(dá)式值實(shí)驗(yàn)4：回溯法學(xué)時(shí)數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實(shí)驗(yàn)題目中選擇若干實(shí)驗(yàn)題目。1.單機(jī)實(shí)驗(yàn)題（1）象棋算式（2）子集和（3）迷宮路徑（4）哈密頓回路2.在線編程題（1）LeetCode216—組合總和III（2）LeetCode39—組合總和（3）3.LeetCode131—分割回文串（4）HDU1027—第k小的排列（5）HDU2553—N皇后問題（6）HDU2616—?dú)⑺拦治铮?）POJ3187—向后數(shù)字和（8）POJ1321—棋盤問題（9）POJ2488—騎士游歷（10）POJ1040—運(yùn)輸問題（11）POJ1129—最少頻道數(shù)實(shí)驗(yàn)5：分支限界法學(xué)時(shí)數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實(shí)驗(yàn)題目中選擇若干實(shí)驗(yàn)題目。1.單機(jī)實(shí)驗(yàn)題（1）原始森林中解救A（2）裝載問題（3）最小機(jī)器重量設(shè)計(jì)問題Ⅰ（4）最小機(jī)器重量設(shè)計(jì)問題Ⅱ（5）貨郎擔(dān)問題2.在線編程題（1）LeetCode847—訪問所有結(jié)點(diǎn)的最短路徑（2）LeetCode1376—通知所有員工所需的時(shí)間（3）HDU1242—救援問題（4）HDU1548—奇怪的電梯（5）HDU1869—六度分離（6）HDU2425—徒步旅行（7）HDU1072—變形迷宮（8）POJ2312—坦克游戲?qū)嶒?yàn)6：貪心法學(xué)時(shí)數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實(shí)驗(yàn)題目中選擇若干實(shí)驗(yàn)題目。1.單機(jī)實(shí)驗(yàn)題（1）蓄欄保留問題（2）刪數(shù)問題（3）求所有最小生成樹（4）改進(jìn)Dijkstra算法（5）字符串的編碼和解碼2.在線編程題（1）LeetCode455—分發(fā)餅干（2）LeetCode135—分發(fā)糖果（3）LeetCode56—合并區(qū)間（4）HDU2037—看電視節(jié)目（5）HDU1009—老鼠的交易（6）HDU3177—裝備問題（7）HDU2111—取寶貝（8）POJ2376—分配清潔班次（9）POJ2726—假日酒店（10）POJ1328—安裝雷達(dá)實(shí)驗(yàn)7：動(dòng)態(tài)規(guī)劃學(xué)時(shí)數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實(shí)驗(yàn)題目中選擇若干實(shí)驗(yàn)題目。1.單機(jī)實(shí)驗(yàn)題（1）矩陣最小路徑和（2）雙核處理問題（3）劃分集合為和相等的兩個(gè)子集合（4）員工分配問題2.在線編程題（1）LeetCode64—最小路徑和（2）LeetCode1289—下降路徑最小和II（3）LeetCode638—大禮包（4）LeetCode139—單詞拆分（5）LeetCode377—組合總和Ⅳ（6）LeetCode354—俄羅斯套娃信封問題（7）LeetCode583—兩個(gè)字符串的刪除操作（8）LetCode122—買賣股票的最佳時(shí)機(jī)II（9）HDU2602—收集物品（10）HDU1114—存錢罐（11）HDU2044—一只小蜜蜂（12）POJ1050—最大子矩形和（13）POJ1157—花店（14）POJ1159—回文